记录编号	42349	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]虫食算	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.065 s
提交时间	2012-09-19 22:03:49	内存使用	0.28 MiB

/*
* 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;
}