比赛 |
20120919dfs |
评测结果 |
AAAAAATAAA |
题目名称 |
虫食算 |
最终得分 |
90 |
用户昵称 |
王者自由 |
运行时间 |
2.583 s |
代码语言 |
C++ |
内存使用 |
1.94 MiB |
提交时间 |
2012-09-19 20:32:59 |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
const int N = 'Z';
int n, a[N], b[N], c[N], t[N], o[N], k;
char s[4][N];
bool u[N], h[N];
bool ok() {
for(int i=n; i>0; i--)
if(t[a[i]] >= 0 && t[b[i]] >= 0 && t[c[i]] >= 0
&& t[c[i]] != (t[a[i]] + t[b[i]]) % n
&& t[c[i]] != (t[a[i]] + t[b[i]] + 1) % n)
return 0;
return 1;
}
void pailie(int x) {
if(x > n) {
int r = 0;
for(int i=n; i>0; i--) {
if((t[a[i]] + t[b[i]] + r) % n != t[c[i]])
return;
r = (t[a[i]] + t[b[i]] + r) / n;
}
for(int i=1; i<=n; i++)
printf("%d ", t[i]);
printf("\n");
exit(0);
}
for(int i=n-1; i>=0; i--)
if(!h[i]) {
t[o[x]] = i;
h[i] = 1;
if(ok()) pailie(x + 1);
h[i] = 0;
t[o[x]] = -1;
}
}
int main() {
freopen("alpha.in", "r", stdin);
freopen("alpha.out", "w", stdout);
scanf("%d\n", &n);
for(int i=1; i<=3; i++)
scanf("%s\n", s[i]);
for(int i=1; i<=n; i++) {
a[i] = s[1][i-1] - 'A' + 1;
b[i] = s[2][i-1] - 'A' + 1;
c[i] = s[3][i-1] - 'A' + 1;
}
for(int i=n; i>0; i--) {
if(!u[a[i]]) u[o[++k] = a[i]] = 1;
if(!u[b[i]]) u[o[++k] = b[i]] = 1;
if(!u[c[i]]) u[o[++k] = c[i]] = 1;
}
for(int i=0; i<n; i++) {
t[i] = -1;
pailie(1);
}
return 0;
}