比赛 |
20120919dfs |
评测结果 |
AAAAAAAAAA |
题目名称 |
虫食算 |
最终得分 |
100 |
用户昵称 |
Makazeu |
运行时间 |
0.095 s |
代码语言 |
C++ |
内存使用 |
3.13 MiB |
提交时间 |
2012-09-19 20:19:12 |
显示代码纯文本
/*
* Problem : alpha
* Contest : NOIP2004
*/
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define Undef -1
using namespace std;
const int MAXN=30;
int N,num[3][MAXN];
string str[3];
int order[MAXN]; /*Record the Search Order*/
int ans[MAXN]; /* Answer */
int Used[MAXN];
inline void init()
{
scanf("%d\n",&N);
for(int k=0;k<=2;k++) {str[k].clear(); cin>>str[k];}
for(int i=1;i<=N;i++)
for(int j=0;j<=2;j++)
num[j][i]=str[j][i-1]-'A'+1;
int used[MAXN]={0}; int top=0;
for(int i=N;i>=1;i--)
for(int j=0;j<=2;j++)
if(!used[num[j][i]])
order[++top]=num[j][i],used[num[j][i]]=1;
}
inline bool check()
{
int next=0;
for(int i=N;i>=1;i--)
{
if((ans[num[0][i]]+ans[num[1][i]]+next)%N!=ans[num[2][i]]) return false;
next=(ans[num[0][i]]+ans[num[1][i]]+next)/N;
}
return (next==0);
}
inline bool jian()
{
for(int i=N;i>=1;i--)
{
if((ans[num[0][i]]==Undef) || (ans[num[1][i]]==Undef) || (ans[num[2][i]])==Undef ) continue;
if((ans[num[0][i]]+ans[num[1][i]])%N==ans[num[2][i]]) continue;
if((ans[num[0][i]]+ans[num[1][i]]+1)%N==ans[num[2][i]]) continue;
return false;
} return true;
}
void dfs(int k)
{
if(k>N)
{
bool flag=check();
if(!flag) return;
for(int i=1;i<=N-1;i++) printf("%d ", ans[i]);
printf("%d\n",ans[N]); exit(0);
}
bool flag;
for(int i=N-1;i>=0;i--)
{
if(Used[i]) continue;
ans[order[k]]=i; flag=jian();
if(!flag) { ans[order[k]]=-1; continue;}
Used[i]=1; dfs(k+1); Used[i]=0; ans[order[k]]=-1;
}
}
inline void solve()
{
for(int i=1;i<=N;i++) ans[i]=Undef;
dfs(1);
}
int main()
{
freopen("alpha.in","r",stdin);
freopen("alpha.out","w",stdout);
init(); solve();
return 0;
}