← 返回题目列表

AtCoder · ddcc2018_qual_d

D. 芯片物语~黄金版~

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

配点: 700 点

問題文

高桥的狗 BISCO 已经在 DISCO 公司工作了 29 年,终于退休了。由于他为公司做出了巨大贡献,武钢总经理授予他“金方芯片”。

该芯片包含一个秘密整数 N 作为数据包含在内,BISCO 是 我知道它是一个小于或等于 N 是 1 以上 10^{12} 的整数。
然而,这个整数 只有总统可以查看 N 的实际值。

BISCO仍然想知道秘密整数,因此武钢总裁给出了以下值作为提示。

  • a_2, a_3, a_4, ..., a_{30} 的 29 值。
  • 但是, a_i 是一个整数 N 的 i 以基数表示的数字总和。

例如, 当 N = 1123 时, N 的 4 以基数表示 101203 ,所以 a_4 = 1 + 0 + 1 + 2 + 0 + 3 = 7 变为。

基于 BISCO 提示的秘密整数 猜猜 N 。
然而,如果有多个可能的秘密整数,则可以输出其中任何一个;如果不存在这样的号码, 输出 invalid 。

制約

  • a_2, a_3, a_4, ..., a_{30} 就是全部 小于或等于 1 以上 500 的整数

入力

输入是按以下格式从标准输入给出的。

a_2
a_3
a_4
:
a_{30}

出力

秘密整数 N (\leq 10^{12}) 可能的数字是 1 输出一。但是,如果不存在这样的数字, 输出 invalid 。


入力例 1

3
5
4
1
5
7
4
9
7
5
3
13
12
11
10
9
8
7
6
5
4
3
2
1
25
25
25
25
25

出力例 1

25

N = 25 是一个可能的秘密整数。

  • 25 的 2 以基数表示 11001 每位数字之和为 3 ,即 相当于 a_2 。
  • 25 的 3 以基数表示 221 每位数字之和为 5 ,即 相当于 a_3 。

该属性是, 直到 a_4 它们的编号最大为 a_{30} 为止也是如此。 请注意


入力例 2

500
30
33
36
39
42
45
48
51
54
57
69
63
66
69
72
75
78
81
84
87
90
93
96
99
102
105
108
111

出力例 2

invalid

a_2 = 500 。
2 用基数表示时,各数字之和为 满足 500 的最小正整数是 2^{500} - 1 ,这是一个秘密整数 是 N 值的上限 比 10^{12} 大得多。
因此,不存在可以作为秘密整数的数字。


入力例 3

23
27
35
31
36
29
55
63
23
61
49
47
86
69
86
111
63
113
63
71
104
93
95
95
111
125
167
111
111

出力例 3

201811232111

201811232111 是一个可能的秘密整数。


入力例 4

14
25
20
13
31
41
30
49
2
61
68
65
67
65
56
65
65
83
27
81
107
101
106
41
126
93
83
121
108

出力例 4

invalid

秘密整数是 10^{12} 请注意(排除这种情况, 1000000000001 是一个可能的秘密整数。)