SWERC14A - GREAT SWERC

no tags 

We want to have a great SWERC at Porto this year and we approached this challenge in several ways. We even framed it as a word addition problem, similar to the classic SEND+MORE=MONEY, where each letter stands for a single digit (0, 1, 2 ... 8, 9) that makes the arithmetic operation correct. In word additions different letters cannot be assigned the same digit and the leftmost letter in a word cannot be zero (0). In particular, a single letter term cannot be zero.

To solve this word addition problem we had to find positive digits for G, S and P, and digits for R, E, A, T, W, C, O, so that each letter has a different digit and results in a correct sum. It turns out that, unlike the classical SEND+MORE=MONEY which has a single solution, GREAT+SWERC=PORTO has six solutions.

T=7, E=3, W=9, G=1, A=0, P=4, S=2, C=8, R=6, O=5
T=7, E=3, W=9, G=2, A=0, P=4, S=1, C=8, R=6, O=5
T=8, E=5, W=1, G=3, A=7, P=9, S=6, C=4, R=0, O=2
T=8, E=5, W=1, G=6, A=7, P=9, S=3, C=4, R=0, O=2
T=9, E=5, W=2, G=1, A=8, P=7, S=6, C=4, R=0, O=3
T=9, E=5, W=2, G=6, A=8, P=7, S=1, C=4, R=0, O=3

Having more than one solution does not make GREAT+SWERC=PORTO a good problem to solve by hand, but it is still a piece of cake for a programmer. Moreover, it gives us another reason to organize SWERC again next year and, who knows, in years to come!

Task

Given a word addition problem, compute the number of solutions (possibly zero).

Input

A line with an integer n, followed by n lines containing a word each with maximum length of 10 letters. The first n - 1 words are the terms to be added and the last line is the result. Words contain only capital letters. If words have different lengths, they must be interpreted as aligning to the right. For instance, in the SEND+MORE=MONEY problem, the D of the first word and E of the second word align with the Y of the final word. You can also assume that the size of the last word is greater than or equal to the maximum size of the preceding words, and moreover, at most ten distinct letters are involved in a word problem.

Constraints

3 ≤ n ≤ 10.

Each word has at most 10 symbols (capital letters). A word problem has at most 10 distinct letters.

Output

A single line with an integer: the number of solutions of the word addition problem given as input.

Examples

Sample Input 1
3
GREAT
SWERC
PORTO

Sample Output 1
6
Sample Input 2
3
SEND
MORE
MONEY

Sample Output 2
1
Sample Input 3
5
TOO
GOOD
TO
BE
TRUE

Sample Output 3
93

Author: José Paulo Leal


hide comments
Scape: 2015-07-22 23:54:09

I agree with mehmetin. These problems surely belong to anywhere but tutorial. A lot of classical problems from Regionals have public solution. I doubt moving them to tutorial would be a good thing to do.

mehmetin: 2015-02-17 14:47:25

Perhaps these problems can be moved to challenge section with code shortening constraints or other types of scoring criteria? It would be better than in tutorial.

Last edit: 2015-02-17 14:48:39
Jacob Plachta: 2014-12-21 05:00:54

Indeed, and this is still being debated.

Miguel Oliveira: 2014-12-18 04:35:51

I also don't think so, but it was due to the solutions being available online and this http://www.spoj.com/forum/viewtopic.php?f=53&t=21828&sid=1937abe045b3f90da98b9d1f27a64622

I didn't have time yet to join the discussion, but will try to do it asap.

mehmetin: 2014-12-18 01:06:21

These problems don't belong to tutorial section.


Added by:Miguel Oliveira
Date:2014-12-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:SWERC 2014