BLUEEQ - Help Blue Mary Please! (Act I)
This morning Blue Mary wrote some equations on a piece of paper and left it on her desk. After solving some problems in SPOJ, she found that her classmate H.L. replaced all characters on the paper with some other ones. H.L. told her he replaced the same characters with the same ones, and different characters with different ones because of his goodness. Now Mary needs your help to get the original equations back.
In Mary's equations, only 13 characters appear: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, *, =. There is one and only one "=" in each equation. In H.L.'s equations, only 13 Latin letters appear: a, b, c, d, e, f, g, h, i, j, k, l, m. All the equations are correct in decimal notation.
For example. If Mary wrote down 2+29=31, H.L. replaced 2 with i, + with l, 9 with k, = with e, 3 with m and 1 with a, we got ilikema.
Input
The first line contains a single integer t. t blocks follow.
To every block, the first line contains a single integer n (1 <= n <= 1000). n lines follow, each contains a string whose length is more than 4 and less than 12.The string contains only a-m and doesn't contain any whitespace.
At least 90% of test cases satisfy that n <= 5.
At least 80% of test cases satisfy that n <= 2.
In at least 70% of test cases, there are at most 5 different characters in all the equations.
Output
If there doesn't exist n equations that can be translated to H.L.'s equations, print a line contains the word noway. Otherwise you should output all the corresponding relations that can be fixed in lexicographic order, see the example.
Example
Input 1 2 abcdec cdefe Output a6 b* d= f+
hint
The two strings can be translated to the following equations possibly:
- 6*2=12 2=1+1
- 6*4=24 4=2+2
- 6*8=48 8=4+4
So the corresponding relations above can be fixed, others can not.
hide comments
Niklas Baumstark:
2013-05-15 16:55:54
Thank you Nenad :) Any comments on the leading zeroes part? |
|
Nenad Bo¾idareviæ:
2013-05-14 07:58:05
I don't think anybody reads these, but let's give it a shot... [Got AC, here are my conclusions]
|
|
Hagen von Eitzen:
2011-06-29 17:38:57
Is '+' also allowed as unary sign?
|
Added by: | Fudan University Problem Setters |
Date: | 2007-04-01 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: C99 ERL JS-RHINO |
Resource: | Chinese National Olympiad in Informatics 2000,Day 2; translated by Blue Mary |