Letter Arithmetic
Time limit1sMemory limit128 MB
Assign distinct digits to letters so that each given letter word plus a second equals a third, then print the three numeric values.
- Level
Medium7 of 10
- Topics
- Backtracking, Math, Bit manipulation, Implementation
- Solved
- No attempts yet
Problem
A popular pencil-and-paper puzzle replaces the digits of an arithmetic statement with letters. For example,
SEND
+MORE
-----
MONEY
represents
9567
+1085
-----
10652
Each letter stands for a single distinct digit, and equal letters always stand for equal digits. Given several groups of three "words," assign a distinct digit to every letter so that the sum of the first two words equals the third word. No word may have the digit 0 assigned to its leading letter.
Input
The first line contains a positive integer , the number of data sets. Each data set consists of three lines, one word per line, where the third word is the sum of the first two. Every word consists of uppercase letters only and is at most 20 letters long.
Output
For each data set, output three lines: the numeric value of the first word, of the second word, and of the third word, in that order. Every data set is guaranteed to have exactly one valid assignment.