/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
以下の条件を満たす正整数 X を 良い整数 とします。
- X を十進法で表記したとき一の位、十の位、\ldots が広義単調減少になっている。
- より厳密には、\displaystyle X=\sum_{i=0}^{\infty} d_i10^i (0\le d_i < 10) を満たす唯一の非負整数列 (d_0,d_1,\ldots) が広義単調減少列になっている。
例えば、 112389 や 1 、777 は良い整数ですが、 443 や 404 は良い整数ではありません。
正整数 N が与えられます。
N の倍数であるような良い整数が存在するか判定し、存在する場合はその最小値を求めてください。
制約
- 1\le N\le 3\times 10^6
- 入力される値は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N の倍数であるような良い整数が存在しない場合は -1 を出力せよ。
存在する場合は N の倍数であるような良い整数の最小値を出力せよ。
入力例 1
21
出力例 1
126
126 は 21 の倍数であり、 6 \geq 2 \geq 1 \geq 0 \geq \ldots が成り立つため良い整数です。 126 未満の 21 の倍数であるような良い整数は存在しないため、 126 を出力してください。
入力例 2
10
出力例 2
-1
入力例 3
3
出力例 3
3
入力例 4
1089
出力例 4
9999999999999999999999
答えが 2^{64} 以上になる場合があります。
Score : 525 points
Problem Statement
A positive integer X is called a good integer if and only if it satisfies the following condition:
- When X is written in decimal notation, the ones digit, tens digit, \ldots form a non-increasing sequence.
- More formally, the unique non-negative integer sequence (d_0,d_1,\ldots) satisfying \displaystyle X=\sum_{i=0}^{\infty} d_i10^i (0\le d_i < 10) forms a non-increasing sequence.
For example, 112389, 1, and 777 are good integers, but 443 and 404 are not good integers.
You are given a positive integer N.
Determine whether there exists a good integer that is a multiple of N, and if it exists, find its minimum value.
Constraints
- 1\le N\le 3\times 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Output
If there does not exist a good integer that is a multiple of N, output -1.
If it exists, output the minimum value of a good integer that is a multiple of N.
Sample Input 1
21
Sample Output 1
126
126 is a multiple of 21, and we have 6 \geq 2 \geq 1 \geq 0 \geq \ldots, so it is a good integer. There does not exist a good integer less than 126 that is a multiple of 21, so output 126.
Sample Input 2
10
Sample Output 2
-1
Sample Input 3
3
Sample Output 3
3
Sample Input 4
1089
Sample Output 4
9999999999999999999999
The answer may be 2^{64} or greater.