游客 Signup | Login
中文 | En

2361 - 虫食算

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 125 MB

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：

       43#9865#045
    +     8468#6633
       44445509678

其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。

<span style="line-height:1.5;">现在，我们对问题做两个限制：</span> 


<span style="line-height:1.5;">首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。</span> 


<span style="line-height:1.5;">其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1。输入数据保证N个字母分别至少出现一次。</span>


            BADC
      +    CRDA
            DCCC

上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解。


<br />

Input

每组输入数据包含4行。第一行是一个正整数N（N<=26），后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。 


<span style="line-height:1.5;">数据规模：</span> 


对于30％的数据，保证有N&lt;＝10；


对于50％的数据，保证有N&lt;＝15；


对于全部的数据，保证有N&lt;＝26。


<span style="line-height:1.5;"></span> 


<br />

Output

每组输出包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C...所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。


Examples

Input Format

5
ABCED
BDACE
EBBAA

Output Format

1 0 3 4 2

Solution C++

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,zm[30],c[5][31];
char c1;
bool f[30],F;
bool jc()
{
	int p=0;
	for(int i=n-1;i>=0;--i)
	{
	  if (zm[c[1][i]]==-1||zm[c[2][i]]==-1||zm[c[3][i]]==-1)return false;
	  int x=zm[c[1][i]]+zm[c[2][i]]+p;
	  if(x%n!=zm[c[3][i]])return true;
	  p=x/n;
	}
	return false;
}
bool jc2()
{
	for(int i=n-1;i>=0;--i)//a+b?c
	  if(zm[c[1][i]]!=-1&&zm[c[2][i]]!=-1&&zm[c[3][i]]!=-1)
	  {
		int x=(zm[c[1][i]]+zm[c[2][i]])%n;
		if(!(x%n==zm[c[3][i]]||(x+1)%n==zm[c[3][i]]))return true;
	  }
	for(int i=n-1;i>=0;--i)//a+?=c
	  if(zm[c[1][i]]!=-1&&zm[c[2][i]]==-1&&zm[c[3][i]]!=-1)
	  {
		int x=(zm[c[3][i]]-zm[c[1][i]]+n)%n;
		if(f[x]&&f[(x-1)%n])return true;
	  }
	for(int i=n-1;i>=0;--i)//?+b=c
	  if(zm[c[1][i]]==-1&&zm[c[2][i]]!=-1&&zm[c[3][i]]!=-1)
	  {
		int x=(zm[c[3][i]]-zm[c[2][i]]+n)%n;
		if(f[x]&&f[(x-1)%n])return true;
	  }
	for(int i=n-1;i>=0;--i)//a+b=?
	  if(zm[c[1][i]]!=-1&&zm[c[2][i]]!=-1&&zm[c[3][i]]==-1)
	  {
		int x=(zm[c[1][i]]+zm[c[2][i]])%n;
		if(f[x]&&f[(x+1)%n])return true;
	  }
	return false;
}
void work(int k,int w)
{
	if(F)return;
	if(jc())return;
	if(jc2())return;
	//if(zm[c[1][0]-65]+zm[c[2][0]-65]>n)return;
	if(k==0&&w==3)
	{
	  for(int i=0;i<n-1;++i)printf("%d ",zm[i]);
	  printf("%d\n",zm[n-1]);F=true;return;
	}
	
	
	if(zm[c[w][k]]!=-1)
	{
	  if(w==3){w=1;--k;}else ++w;
	  work(k,w);
	  if(w==1){w=3;++k;}else --w;
	}
	else
	{
	  for(int i=n-1;i>=0;--i)
	    if(!f[i])
	    {
		  zm[c[w][k]]=i,f[i]=true;
		  if(w==3){w=1;--k;}else ++w;
		  work(k,w);
		  if(w==1){w=3;++k;}else --w;
		  zm[c[w][k]]=-1;f[i]=false;
	    }
	}
	
}
int main()
{
	memset(c,0,sizeof(c));
	scanf("%d",&n);
	for(int i=1;i<=3;++i)
	  for(int j=0;j<n;++j)
	    {cin>>c1;c[i][j]=c1-65;}
	F=false;
	memset(f,0,sizeof(f));
	for(int i=0;i<n;++i)zm[i]=-1;
	work(n-1,1);
	return 0;
}
请先登陆