DMOPC '15 Contest 5 P3 - All Your Base

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Okabe likes writing notes for himself. Since he writes about strange things and does not want others to think he is weird, he encodes all his messages in his own super-secret format. Unfortunately for Okabe, you — being an amazing cryptanalyst — have figured out his scheme.

First, he maps a character to an integer D, and then converts it into another integer E by changing its base. He creates a random list A of N integers, where A_{i-1} is stored in base A_i, and E is stored in base A_0. That is,

\displaystyle D = E_{A_{0_{\ A_{1_{\ \cdots_{\ A_{N-1}}}}}}}

You've gotten your hands on some of Okabe's notes, and would like to decrypt some E values, given A. Can you do it?


The notation for representing a number X in base Y is X_Y.

Input Specification

The first line of input will contain the integers E and N (1 \le N \le 10).
The next and final line of input will contain N space-separated integers making up A, with the i-th integer representing A_i (1 \le A_{i_{\ 10}} \le 10). A_{N-1} is always given in base 10, and it is guaranteed that E can be converted (for every digit d in A_{i-1}, d < A_{i} unless A_i = 1, when d=1).

Output Specification

A single integer, D (0 \le D \le 10^9).

Sample Input 1

5 3
10 10 10

Sample Output 1


Sample Input 2

5000 4
7 1001 10 2

Sample Output 2



Working your way up from A_{N-1},
\displaystyle 5000_{\ 7_{\ 1001_{\ 10_{\ 2}}}} = 5000_{\ 7_{\ 1001_{\ 2}}} = 5000_{\ 7_{\ 9}} = 5000_{\ 7} = 1715

10_2 = 2.
1001_2 = 9.
7_9 = 7.
5000_7 = 1715.


There are no comments at the moment.