実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
以下の条件を満たす正の整数 n を、 等差数 と呼びます。
- (n を先頭に余計な 0 を付けずに 10 進法で表記した際、) n の上から i 桁目を d_i とする。このとき、 n が k 桁の整数であったとすると、 (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) が成立する。
- この条件は、「 数列 (d_1,d_2,\dots,d_k) が等差数列である」と言い換えることができる。
- 但し、 n が 1 桁の整数である時、 n は等差数であるものとする。
たとえば、 234,369,86420,17,95,8,11,777 は等差数ですが、 751,919,2022,246810,2356 は等差数ではありません。
等差数のうち、 X 以上で最小のものを求めてください。
制約
- X は 1 以上 10^{17} 以下の整数である
入力
入力は以下の形式で標準入力から与えられる。
X
出力
答えを整数として出力せよ。
入力例 1
152
出力例 1
159
152 以上で最小の等差数は 159 です。
入力例 2
88
出力例 2
88
X 自身が等差数である場合もあります。
入力例 3
8989898989
出力例 3
9876543210
Score : 500 points
Problem Statement
Let us call a positive integer n that satisfies the following condition an arithmetic number.
- Let d_i be the i-th digit of n from the top (when n is written in base 10 without unnecessary leading zeros.) Then, (d_2-d_1)=(d_3-d_2)=\dots=(d_k-d_{k-1}) holds, where k is the number of digits in n.
- This condition can be rephrased into the sequence (d_1,d_2,\dots,d_k) being arithmetic.
- If n is a 1-digit integer, it is assumed to be an arithmetic number.
For example, 234,369,86420,17,95,8,11,777 are arithmetic numbers, while 751,919,2022,246810,2356 are not.
Find the smallest arithmetic number not less than X.
Constraints
- X is an integer between 1 and 10^{17} (inclusive).
Input
Input is given from Standard Input in the following format:
X
Output
Print the answer as an integer.
Sample Input 1
152
Sample Output 1
159
The smallest arithmetic number not less than 152 is 159.
Sample Input 2
88
Sample Output 2
88
X itself may be an arithmetic number.
Sample Input 3
8989898989
Sample Output 3
9876543210