ICPC NAQ 2015 A - All About That Base

View as PDF

Submit solution

Points: 7
Time limit: 0.6s
Memory limit: 1G

Problem type
ICPC North America Qualifier 2015, Problem A
A pointless picture

The base (or radix) of a positional numeral system is the number of symbols that can be used to represent a number in that system. The base 10 system (also known as decimal) uses 10 distinct symbols: 0,1,\dots,9. For example, we interpret the number 72\,345 as:

\displaystyle 7 \times 10^4 + 2 \times 10^3 + 3 \times 10^2 + 4 \times 10^1 + 5 \times 10^0.

This example illustrates that in base 10 the symbol at place P \ge 0 (starting from the right) is multiplied by 10^P to get its value. More generally, in base B we use B symbols to represent 0,\dots,B-1, and the symbol at the P^{th} place is multiplied by B^P to get its value.

Other bases commonly used in computation include base 2 (or binary, using symbols 0 and 1), base 8 (or octal, using symbols 07), and base 16 (or hexadecimal, using symbols 09 and af). In bases higher than 10, letters represent the higher values. Thus in hexadecimal af represent the decimal values 1015, and in bases \ge 36 the letter z represents the decimal value 35.

Your job is to determine the bases in which given arithmetic expressions are valid. We define an expression as valid in base B if two conditions are true. First, all the operands used are interpretable in base B as having values in the decimal range [1,2^{32}-1]. Second, the expression is true. Any arbitrary expression might be valid in zero, one, or more bases. In this problem we will only consider bases 136, where base 1 is unary.

Note that following the convention listed above, unary would consist of a single symbol: 0. In this problem, unary numbers use the symbol 1 rather than 0 (think "tally marks"). E.g., 111 in unary is equivalent to the decimal number 3 and 1111111 in unary is equivalent to the decimal number 7.

Input Specification

Input for this problem starts with a line containing an integer 0 \le N \le 20. The following N lines each contain an arithmetic expression with the following form:

\displaystyle X \operatorname{op} Y = Z

where X, Y, and Z are positive, whole numbers consisting of 1 to 100 symbols from the set 09 and az, and \operatorname{op} is one of the four operators +, -, *, /. For each statement there is at least one base 1 \le B \le 36 such that X, Y, and Z can all be interpreted in base B as having values in the decimal range [1,2^{32}-1].

Output Specification

For each expression, list the bases in which the expression is valid (sorted in ascending base order) or the word invalid if the expression is not valid in any of the bases 136. Use symbols 19, then az, then 0 to represent bases 136 (with the last symbol, 0, representing base 36).

Sample Input

8
6ef + d1 = 7c0
3 / 2 = 1
444 / 2 = 222
10111 * 11 = 1000101
10111 * 11 = 111221
5k - 1z = 46
1111111111 - 1111111 = 111
2048 - 512 = 1536

Sample Output

g
invalid
56789abcdefghijklmnopqrstuvwxyz0
2
3456789abcdefghijklmnopqrstuvwxyz0
invalid
1
a
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.