Yet Another A+B Problem
Time Limit : 10 Second
Memory Limit : 128 MB
Submission: 139
Solved: 34
- Description
- We all have come across A+B Problem many times. This time, you are to solve another A+B Problem. An addition rebus is a puzzle where you get an addition equation, like "ABC+CBA=BDB". And you need to replace each letter with a digit (from 0 through 9) in such a way that:
- Equal letters are replaced with equal digits.
- Different letters are replaced with different digits.
- None of the resulting numbers starts with 0, unless the entire number is just 0.
- The resulting equation holds.
Now you are given N addition rebuses, and you are to tell me the maximum number X that there exists a map from each letter to a digit satisfying first X equations but there exists none satisfying first X+1 equations. If there exists a sequence satisfying all the given equations, then number X should be the number of all the equations given. And if there exists none sequence satisfying the first equation, then number X should be 0. - Input
- The input consists of multiple test cases. The first line of input contains an integer T (T <= 10), which is the number of test cases.
The first line of each test case contains the number N (N <= 10), indicating the total number of equations.
The next N line each contains an addition rebus described above. Equations are consisted of numbers (represented by capital letters) and operators ("+" and "="). You can assume that there exists no more than 10 different letters in each test case and the length of each number is a positive integer less or equal to 20. - Output
- For each test case, your program should output one line containing the maximum number X as we described above.
- sample input
-
2 2 AAA+BBB=CCC AAA+CCC=DDD 3 ABC+CBA=DDD AAA+BBB=EEE ABA+CBC=EEE
- sample output
-
2 2
- hint
- source
- <a href="http://aifreedom.com/">Ai.Freedom</a>