2022는 무엇이 특별할까?

면접 대비

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

요약

N과 진법 d가 주어질 때, d진법으로 나타냈을 때 0부터 d-1까지 각 숫자가 정확히 한 번씩 쓰이는 가장 작은 수를 N보다 크게 구합니다.

문제

신년대회의 개최일은 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_{n} a_{n - 1} \dots a_{1} a_{0}_{(d)}$ 라는 것은, $A = a_n \times d^n + a_{n-1} \times d^{n-1} + \cdots + a_1 \times d^1 + a_0 \times d^0$ $A = a_{n} \times d^{n} + a_{n - 1} \times d^{n - 1} + \dots + a_{1} \times d^{1} + a_{0} \times 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$ 이 각각 정확히 한 번씩 나온다는 뜻이다.