D - 隠された等差数列
Editorial
/
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
シカのAtCoDeerくんはある日N項からなる数字列{d_i} (0≦i≦N-1)を見つけました。AtCoDeerくんの勘によると、この裏には非負整数からなる等差数列が隠れています。具体的には、
- 非負整数A,B,正整数Xをとる。
- a_0 = A , a_i = a_{i-1} + B (1≦i≦N-1) とa_iを定める。
- すると、i (0≦i≦N-1) に対し、a_iの(十進表記で)下からX桁目がd_iに等しい。
AtCoDeerくんは、このような条件を満たす等差数列の内、初項(すなわちA)が最小のものを求めることにした。
制約
- 1≦N≦10^4
- 各0≦i≦N-1に対し,d_iは0以上9以下の整数
- d_0≠0
入力
入力は以下の形式で標準入力から与えられる。
d_0d_1....d_{N-1}空白文字で区切られずに与えられることに注意せよ。
出力
条件を満たす等差数列の内の初項の最小値を出力せよ。そのような等差数列が存在しない場合は-1
を出力せよ。
入力例1
6925814703
出力例1
6
A=6,B=3,X=1は条件を満たし、これがAの最小です。
入力例2
6925814704
出力例2
61
A=61,B=31,X=2が条件を満たします。
入力例3
6925814705
出力例3
-1
条件を満たす等差数列はありません。
入力例4
9
出力例4
9