Problem 1122 : What is the Number in my Mind ?

問題概要

解法

答えの数字は最大でも10!通り（=360万）なのでnext_permutationで回しながら全通り調べて間に合うか……と思ったら間に合わなかったので、使う数字の候補を絞って少し枝刈りしたら通った。

ソースコード

int l,n,hit[100],blow[100];
bool use[100][10];
char tmp[11],in[100][11],ans[11];

int main()
{
	while(scanf("%d%d",&l,&n),l)
	{
		rep(i,n)
		{
			scanf("%s%d%d",in[i],hit+i,blow+i);
			rep(j,10)use[i][j]=0;
			rep(j,l)use[i][in[i][j]-'0']=1;
		}
		
		int cand=0,cbit=0;
		rep(i,1<<10)
		{
			rep(j,n)
			{
				int cnt=0;
				rep(k,10)if((i&1<<k)&&use[j][k])cnt++;
				if(cnt!=hit[j]+blow[j])goto NI;
			}
			cand|=i;
			NI:;
		}
		ans[0]=0;
		rep(i,10)if(cand&1<<i)tmp[cbit++]=i+'0';
		do
		{
			rep(i,n)
			{
				int h=0,b=0;
				rep(j,l)
				{
					if(tmp[j]==in[i][j])h++;
					else if(use[i][tmp[j]-'0'])b++;
				}
				if(h!=hit[i]||b!=blow[i])goto NEXT;
			}
			if(ans[0]!=0)
			{
				ans[0]=0; goto END;
			}
			rep(i,l)ans[i]=tmp[i];
			
			NEXT:;
			reverse(tmp+l,tmp+cbit);
		}while(next_permutation(tmp,tmp+cbit));
		
		END:
		ans[l]=0;
		if(ans[0])printf("%s\n",ans);
		else puts("NO");
	}
	
	return 0;
}