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に等しい。
ここで、非負整数nの下からx桁目とは、 (n/10^{x-1})%10 のことを指す(ただし, /は除算(切り捨て), %はあまりを取る操作)。 例えば、102の下から一桁目は2,二桁目は0,三桁目は1,四桁目は0,百桁目は0である。

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