시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
40 초 128 MB 8 3 2 33.333%

문제

단어 덧셈이란 905 + 125 = 1030과 같은 덧셈의 각 숫자를 알파벳으로 바꾼 것이다.

9를 A로, 0을 C로, 5를 M으로, 1을 I로, 2를 B로, 0을 C로, 3을 P로 바꾸면 다음과 같이 된다.

ACM + IBM = ICPC

이렇게 905 + 125 = 1030의 경우에는 바꾸는 방법이 총 4가지가 있다.

방법 A B C I M P
방법 1 9 2 0 1 5 3
방법 2 9 3 0 1 5 4
방법 2 9 6 0 1 5 7
방법 2 9 7 0 1 5 8

 

단어 덧셈이 주어졌을 때, 이 단어 덧셈을 푸는 방법의 수를 구하는 프로그램을 작성하시오. 단, 다음 조건을 만족해야 한다.

1. 덧셈의 각 항은 숫자 '0'-'9'로 이루어져 있다. 모든 숫자는 알파벳 'A'-Z'로 바뀌어져 있다.

2. 한 알파벳은 하나의 숫자만을 나타낼 수 있다. 또, 어떤 숫자에 해당하는 알파벳은 반드시 하나 이어야 한다.

3. 0을 제외한 숫자는 0으로 시작할 수 없다. 즉, 00이나 0123과 같은 경우는 허용하지 않는다.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 테스트 케이스의 마지막 줄에는 0이 주어진다.

각 테스트 케이스는 첫째 줄에 단어의 개수 N이 주어지고, 그 다음 줄에는 단어 N개가 주어진다. 단어는 알파벳 'A'-'Z'로만 이루어져 있다.

각 단어는 다음과 같은 방정식을 나타낸다.

단어1+단어2+...+단어N-1 = 단어N

N은 2보다 크고, 13보다 작다. 단어의 길이는 0보다 크고, 9보다 작다. 단어에 등장하는 서로 다른 알파벳의 개수는 0보다 크고, 11보다 작다.

출력

각 테스트 케이스에 대해서, 단어 덧셈을 풀 수 있는 방법의 수를 출력한다.

예제 입력

3
ACM
IBM
ICPC
3
GAME
BEST
GAMER
4
A
B
C
AB
3
A
B
CD
3
ONE
TWO
THREE
3
TWO
THREE
FIVE
3
MOV
POP
DIV
9
A
B
C
D
E
F
G
H
IJ
0

예제 출력

4
1
8
30
0
0
0
40320

힌트

출처

ACM-ICPC > Regionals > Asia > Japan > Domestic Contest > 2009 Domestic Contest C번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kazel