AT_ddcc2018_qual_d チップ・ストーリー　～黄金編～

[problemUrl]: https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d 高橋君の飼い犬の BISCO は, ディスコ株式会社に 29 年務め, ついに退職の時を迎えた. 彼は会社に大きく貢献したため, 社長の WISCO から「黄金の正方形チップ」をプレゼントされた. このチップには, 秘密の整数 $ N $ がデータとして入っており, BISCO は $ N $ が $ 1 $ 以上 $ 10^{12} $ 以下の整数であることを知っている. しかし, この整数 $ N $ の実際の値は社長しか閲覧することができない. それでも BISCO が秘密の整数を知りたがったので, 社長の WISCO は, 以下の値をヒントとして与えた. - $ 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} $

秘密の整数 $ N\ (\leq\ 10^{12}) $ としてあり得る数を $ 1 $ つ出力せよ. ただし, そのような数が存在しない場合は `invalid` と出力せよ.

### 制約 - $ a_2,\ a_3,\ a_4,\ ...,\ a_{30} $ はすべて $ 1 $ 以上 $ 500 $ 以下の整数 ### Sample Explanation 1 $ N\ =\ 25 $ は, 秘密の整数としてあり得る数である. - $ 25 $ を $ 2 $ 進数で表すと `11001` となり, 各位の桁の和は $ 3 $ で, これは $ a_2 $ に等しい. - $ 25 $ を $ 3 $ 進数で表すと `221` となり, 各位の桁の和は $ 5 $ で, これは $ a_3 $ に等しい. この性質は, $ a_4 $ から $ a_{30} $ までについても同じように満たされる. ### Sample Explanation 2 $ a_2\ =\ 500 $ に注目する. $ 2 $ 進数で表したときに各位の桁の和が $ 500 $ となるような最小の正の整数は $ 2^{500}\ -\ 1 $ で, これは秘密の整数 $ N $ の値の上限である $ 10^{12} $ を大きく超える. したがって, 秘密の整数としてありうる数は存在しない. ### Sample Explanation 3 $ 201811232111 $ は, 秘密の整数としてあり得る数である. ### Sample Explanation 4 秘密の整数は $ 10^{12} $ 以下であることに注意せよ. (この条件を除けば, $ 1000000000001 $ が秘密の整数としてあり得る数となる.)