ICPC North America Qualifier 2015, Problem A
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 system (also known as decimal) uses distinct symbols: . For example, we interpret the number as:
This example illustrates that in base the symbol at place (starting from the right) is multiplied by to get its value. More generally, in base we use symbols to represent , and the symbol at the place is multiplied by to get its value.
Other bases commonly used in computation include base (or binary, using symbols and ), base (or octal, using symbols –), and base (or hexadecimal, using symbols – and –). In bases higher than , letters represent the higher values. Thus in hexadecimal – represent the decimal values –, and in bases the letter represents the decimal value .
Your job is to determine the bases in which given arithmetic expressions are valid. We define an expression as valid in base if two conditions are true. First, all the operands used are interpretable in base as having values in the decimal range . 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 –, where base is unary.
Note that following the convention listed above, unary would consist of a single symbol: . In this problem, unary numbers use the symbol rather than (think "tally marks"). E.g., in unary is equivalent to the decimal number and in unary is equivalent to the decimal number .
Input Specification
Input for this problem starts with a line containing an integer . The following lines each contain an arithmetic expression with the following form:
where , , and are positive, whole numbers consisting of to symbols from the set – and –, and is one of the four operators +
, -
, *
, /
. For each statement there is at least one base such that , , and can all be interpreted in base as having values in the decimal range .
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 –. Use symbols –, then –, then to represent bases – (with the last symbol, , representing base ).
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
Comments