← 返回题目列表

AtCoder · arc055_d

D. 隐藏的算术级数

中文机器翻译题面 查看原题

問題文

有一天,鹿 AtCoDeerN由术语组成的数字字符串 找到{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-kun 计算第一项(即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