/ 
実行時間制限: 5 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
英小文字からなる文字列 S_1,S_2,S_3 が与えられます。覆面算 S_1+S_2=S_3 を解いてください。
正確には、次の 3 つの条件をすべて満たすような正の整数の組 N_1,N_2,N_3 が存在するか判定し、存在するならばそのうち 1 つを求めてください。
ここで、N_1, N_2, N_3 を (先頭に余分な 0 をつけないで) 十進表記した文字列をそれぞれ N'_1, N'_2, N'_3 とします。
- N'_i の文字数は、S_i の文字数に等しい
- N_1+N_2=N_3 を満たす
- S_i の x 文字目と S_j の y 文字目が等しいとき、またその時に限り、N'_i の x 文字目と N'_j の y 文字目が等しい
制約
- S_1,S_2,S_3 は英小文字のみからなる長さ 1 以上 10 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 S_3
出力
条件を満たすような正整数の組 N_1,N_2,N_3 が存在するならば、そのような組の 1 つを改行区切りで出力せよ。
存在しないなら、代わりに UNSOLVABLE と出力せよ。
入力例 1
a b c
出力例 1
1 2 3
(N_1, N_2, N_3) = (4,5,9) などを出力しても正解となります。(1,1,2) は 3 つ目の条件を満たしていない (a,b がともに 1 に対応している) ため、不正解となります。
入力例 2
x x y
出力例 2
1 1 2
(N_1, N_2, N_3) = (3,3,6) などを出力しても正解となります。(1,2,3) は 3 つ目の条件を満たしていない (1,2 がともに x に対応している) ため、不正解となります。
入力例 3
p q p
出力例 3
UNSOLVABLE
入力例 4
abcd efgh ijkl
出力例 4
UNSOLVABLE
入力例 5
send more money
出力例 5
9567 1085 10652
Score : 400 points
Problem Statement
Given strings S_1,S_2,S_3 consisting of lowercase English letters, solve the alphametic S_1+S_2=S_3.
Formally, determine whether there is a triple of positive integers N_1, N_2, N_3 satisfying all of the three conditions below, and find one such triple if it exists.
Here, N'_1, N'_2, N'_3 are strings representing N_1, N_2, N_3 (without leading zeros) in base ten, respectively.
- N'_i and S_i have the same number of characters.
- N_1+N_2=N_3.
- The x-th character of S_i and the y-th character of S_j is the same if and only if the x-th character of N'_i and the y-th character of N'_j are the same.
Constraints
- Each of S_1, S_2, S_3 is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S_1 S_2 S_3
Output
If there is a triple of positive integers N_1, N_2, N_3 satisfying the conditions, print one such triple, using newline as a separator.
Otherwise, print UNSOLVABLE instead.
Sample Input 1
a b c
Sample Output 1
1 2 3
Outputs such as (N_1, N_2, N_3) = (4,5,9) will also be accepted, but (1,1,2) will not since it violates the third condition (both a and b correspond to 1).
Sample Input 2
x x y
Sample Output 2
1 1 2
Outputs such as (N_1, N_2, N_3) = (3,3,6) will also be accepted, but (1,2,3) will not since it violates the third condition (both 1 and 2 correspond to x).
Sample Input 3
p q p
Sample Output 3
UNSOLVABLE
Sample Input 4
abcd efgh ijkl
Sample Output 4
UNSOLVABLE
Sample Input 5
send more money
Sample Output 5
9567 1085 10652