/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
正整数 n の桁和を、n を 10 進法で表したときの各桁の和と定義します。例えば 2025 の桁和は 2 + 0 + 2 + 5 = 9 です。
正整数 n が n の桁和で割り切れる時、n を 良い整数 と呼びます。例えば 2025 はその桁和である 9 で割り切れるので良い整数です。
正整数の組 (a, a+1) であって a と a+1 が共に良い整数であるものを 双子の良い整数 と呼びます。例えば (2024, 2025) は双子の良い整数です。
正整数 N が与えられます。N \leq a かつ a + 1 \leq 2N であるような双子の良い整数 (a, a + 1) を発見してください。そのような (a, a + 1) が存在しない場合はそのことを報告してください。
制約
- N は 1 以上 10^{100000} 未満の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
問題文の条件を満たす (a, a+1) が存在する場合は a を、存在しない場合は -1 を出力せよ。a は leading-zeros を省略した表現で出力する必要がある点に注意せよ。
条件を満たす (a, a+1) が複数存在する場合はどれを出力してもよい。
入力例 1
5
出力例 1
8
(8, 9) は問題文の条件を満たす双子の良い整数です。他にも (5, 6), (6, 7), (7, 8), (9, 10) が条件を満たします。
入力例 2
21
出力例 2
-1
問題文の条件を満たす双子の良い整数は存在しません。
入力例 3
1234
出力例 3
2024
(2024, 2025) は問題文の条件を満たす双子の良い整数です。
入力例 4
1234567890123456789012345678901234567890
出力例 4
1548651852734633803438094164372911259190
Score : 500 points
Problem Statement
The digit sum of a positive integer n is defined as the sum of its digits when n is written in decimal. For example, the digit sum of 2025 is 2 + 0 + 2 + 5 = 9.
A positive integer n is called a good integer if it is divisible by its digit sum. For example, 2025 is a good integer because it is divisible by its digit sum of 9.
A pair of positive integers (a, a+1) is called twin good integers if both a and a+1 are good integers. For example, (2024, 2025) is twin good integers.
You are given a positive integer N. Find a pair of twin good integers (a, a + 1) such that N \leq a and a + 1 \leq 2N. If no such pair exists, report that fact.
Constraints
- N is an integer at least 1 and less than 10^{100000}.
Input
The input is given from Standard Input in the following format:
N
Output
If there exists such a pair (a, a+1), output a. Otherwise, output -1. Do not print leading zeros.
If there are multiple such pairs, you may print any.
Sample Input 1
5
Sample Output 1
8
(8, 9) is a valid pair of twin good integers satisfying the conditions. Other examples include (5, 6), (6, 7), (7, 8), (9, 10).
Sample Input 2
21
Sample Output 2
-1
No pair of twin good integers satisfies the conditions.
Sample Input 3
1234
Sample Output 3
2024
(2024, 2025) is a valid pair of twin good integers.
Sample Input 4
1234567890123456789012345678901234567890
Sample Output 4
1548651852734633803438094164372911259190