2022는 무엇이 특별할까?

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N보다 크면서 d진법으로 표현했을 때 0부터 d-1까지 모든 숫자가 정확히 한 번씩 나오는 가장 작은 수를 찾는다.

문제

백준 온라인 저지의 신년대회 Hello, BOJ 2022!의 개최일은 2022년 1월 15일이다. 준겸이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2022가 무언가 특별하다는 사실을 깨달았다.

그렇다. $2022$ 를 $5$ 진법으로 표현하면 ${31042}\_{(5)}$ 로, $5$ 진법의 각 숫자인 $0$ , $1$ , $2$ , $3$ , $4$ 가 모두 한 번씩 나타난다. 다음에 이런 년도가 오려면 2054년이 되어야 한다.

수 $N$ 과 진법 $d$ 가 주어진다. 당신은 수 $N$ 보다 크면서, $d$ 진법으로 표현했을 때 $d$ 진법의 숫자가 모두 정확히 한 번씩 등장하는 가장 작은 수를 찾아야 한다. 단, 수를 표기할 때는 앞에 불필요한 0이 존재해서는 안 된다.

첫 번째 줄에 수 $N$ 과 진법 $d$ 가 공백을 사이에 두고 $10$ 진법으로 주어진다.

첫 번째 줄에 $N$ 보다 크면서 $d$ 진법으로 표현했을 때 $d$ 진법의 숫자가 모두 정확히 한 번씩 등장하는 수 중 가장 작은 것을 $10$ 진법으로 출력한다.

만약 그런 수가 존재하지 않는다면, 첫 번째 줄에 $-1$ 을 대신 출력한다.

양의 정수 $A$ $A$ 를 $d$ $d$ 진법으로 표현한 결과가 ${a\_n a\_{n-1} \cdots a\_1 a\_0}\_{(d)}$ $a_na_n - 1 \dots a_1 a_0_(d)$ 라는 의미는, $A = a\_n \times d^n + a\_{n-1} \times d^{n-1} + \cdots + a\_1 d^1 + a\_0 d^0$ $A = a_n \times d^{n} + a_n - 1 \times d^{n - 1} + \dots + a_1 d^{1} + a_0 d^{0}$ 이라는 의미이다. 단, $a\_n \neq 0$ $a_n \neq = 0$ 이다.
- 예를 들어, $2022 = 3 \times 5^4 + 1 \times 5^3 + 0 \times 5^2 + 4 \times 5^1 + 2 \times 5^0 = 31042\_{(5)}$ 이다.
$d$ 진법의 숫자는 $0$ 이상 $d$ 미만의 숫자를 의미한다.
$A$ 를 $d$ 진법으로 표현했을 때 $d$ 진법의 숫자가 모두 정확히 한 번씩 등장한다는 의미는, $A = {a\_n a\_{n-1} \cdots a\_1 a\_0}\_{(d)}$ 이라고 썼을 때, $a\_n, a\_{n-1}, \cdots, a\_0$ 에서 $0, 1, \cdots, d-1$ 이 각각 정확히 한 번씩 등장한다는 의미이다.