Word Addition
Time limit40sMemory limit128 MB
Count letter-to-digit assignments that make a cryptarithmetic addition of up to 12 words valid, with no leading zeros and distinct digits per letter.
- Level
Medium7 of 10
- Topics
- Backtracking, Brute force, Math, String
- Solved
- No attempts yet
Problem
A word addition is an addition such as 905 + 125 = 1030 in which every digit has been replaced by a letter.
For example, replacing 9 with A, 0 with C, 5 with M, 1 with I, 2 with B, and 3 with P turns the equation above into:
ACM + IBM = ICPC
For 905 + 125 = 1030, there are 4 different ways to turn the letters back into digits.
Given a word addition, write a program that counts how many digit assignments make the equation hold. The assignment must satisfy all of the following conditions.
- Every term of the addition is made of the digits '0' through '9', and every digit has been replaced by a letter from 'A' through 'Z'.
- Each letter stands for exactly one digit, and different letters stand for different digits. In other words, at most one letter maps to any given digit.
- A number other than 0 may not start with 0, so writings such as 00 or 0123 are not allowed. (The single digit 0 is allowed.)
Input
The input consists of several test cases. Each test case is given as follows.
- The first line contains the number of words, N.
- Then N words follow. Each word consists only of the letters 'A' through 'Z'.
These N words represent the equation (word 1) + (word 2) + ... + (word N-1) = (word N); that is, the last word equals the sum of all the preceding words.
N satisfies 2 < N < 13, the length of each word is greater than 0 and less than 9, and the number of distinct letters that appear in one test case is greater than 0 and less than 11.
The last line of the input contains a single 0, which is not processed.
Output
For each test case, print on its own line the number of digit assignments that make the word addition hold.