Submission #00003

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
int N, Size;
string s[12];
int rec(int idx, int md, int sum, int used, vector< int >& conb) // 場所, 繰り上がり, 使った数字
{
for(int i = 0; i < N; i++) if(s[i].size() != 1 && conb[s[i][s[i].size() - 1]] == 0) return(0);
if(idx == s[N - 1].size()) return(sum == 0);
int ret = 0;
for(int i = md; i < N - 1; i++) {
if(s[i].size() <= idx) continue;
if(conb[s[i][idx]] != -1) {
sum += conb[s[i][idx]];
} else {
for(int j = 0; j < 10; j++) {
if((used >> j) & 1) continue;
conb[s[i][idx]] = j;
ret += rec(idx, i + 1, sum + j, used|(1 << j), conb);
conb[s[i][idx]] = -1;
}
return(ret);
}
}
int digit = sum % 10;
if(conb[s[N - 1][idx]] == -1) {
if((used >> digit) & 1) return(0);
conb[s[N - 1][idx]] = digit;
ret = rec(idx + 1, 0, sum / 10, used|(1 << digit), conb);
conb[s[N - 1][idx]] = -1;
} else {
if(digit != conb[s[N - 1][idx]]) return(0);
ret = rec(idx + 1, 0, sum / 10, used, conb);
}
return(ret);
}
int main()
{
while(cin >> N, N) {
Size = 0;
for(int i = 0; i < N; i++) {
cin >> s[i];
reverse(s[i].begin(), s[i].end());
if(i != N - 1) Size = max< int >(Size, s[i].size());
}
vector< int > conb(128, -1);
if(Size > s[N - 1].size()) cout << 0 << endl;
else cout << rec(0, 0, 0, 0, conb) << endl;
}
}

ステータス

項目 データ
問題 0003 - 覆面算
ユーザー名 I dont any
投稿日時 2015-10-23 13:43:02
言語 C++11
状態 Accepted
得点 20
ソースコード長 1427 Byte
最大実行時間 731 ms
最大メモリ使用量 552 KB

セット

セット 得点 Cases
1 ALL 20 / 20 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
c1 AC 564 ms 476 KB
1
c2 AC 731 ms 448 KB
1
c3 AC 605 ms 552 KB
1
c4 AC 654 ms 536 KB
1