National Olympiad in Informatics, China, 2000

Day 2, Problem 3 - Symbol Deciphering

Archeologists have discovered that the several thousand-year-old mathematics of the ancient Mei civilization was extremely advanced. They understood methods of addition and multiplication for multi-digit numbers. Their rules for representing expressions and performing calculations are exactly the same as those used in the modern day (addition of integers are in base-10, the leftmost digit is the most-significant, the highest digit cannot be zero; expressions are infix, multiplication comes before addition, etc.), with the only exception being that mathematical symbols themselves are written differently. There is sufficient evidence to show that ancient Mei mathematics uses a total of 13 operators which have a one-to-one correspondence to the modern day symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, and =. To simplify the representations of the symbols, we shall use the first 13 alphabetical letters a, b, … m in place of these symbols (known as the ancient Mei mathematical symbols). The problem is, no one currently knows the general relationship for matching the ancient Mei mathematical symbols to modern mathematical symbols.

On a stone wall, archaeologists have discovered a set of equations expressed using the ancient Mei symbols. They have concluded that each row contains only one equal sign, the left and right sides of each equal sign contain mathematical expressions (containing only numbers and operators), and that expressions on the two sides of equal signs are equivalent.

Assuming that this set of equations is successful, please write a program that deciphers the relationship between ancient Mei mathematical symbols and modern mathematical symbols.

Input Format

The first line of input contains an integer N (1 ≤ N ≤ 1000). Each of the following N lines will contain an equation. Each equation will consist of as few as 5 characters and as many as 11 characters.

Output Format

If there does not exist a possible relationship that satisfies the set of equations, output "noway" (without quotes) on a single line.
If there exist a possible mapping that satisfies the set of equations, output all the mappings between ancient Mei symbols and modern symbols that are known for certain. Each line should contain two characters, where the first character is an ancient Mei mathematical symbol and the second character is the modern mathematical symbol to which it is mapped. Output the mappings in alphabetical order.

Sample Input

2
abcdec
cdefe

Sample Output

a6
b*
d=
f+

Explanation

In the sample above, the possibilities for the equations in modern symbols are {6*2=12, 2=1+1}, {6*4=24, 4=2+2}, and {6*8=48, 8=4+4}. It can be seen that the confirmed relationships only consist of a mapping of a to 6, b to *, d to =, and f to +, which should be outputted. Although possible mappings for {c, e} can be successfully found, there is no unique relationship for them, and thus they should not be outputted. The other ancient Mei mathematical symbols {g, h, …, m} are completely unverifiable, and also should not be outputted.

All Submissions
Best Solutions

Point Value: 40 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 06, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)