[USACO 2010 Mar B]MasterMind

For example, suppose codemaker's secret number is 2351. If codebreaker guesses 1350, the codemaker provides the feedback "2 1", since 3 and 5 are in correct locations in the number, and 1 is in the wrong location. As another example, if the secret number is 11223 (in a five-digit version of mastermind) and the guess is 12322, then the feedback would be "2 2". Below is a sample game where the secret number is 2351: Correct digits in correct location | Correct digits in wrong location Guess | | 3157 1 2 1350 2 1 6120 0 2 2381 3 0 2351 4 0 For this task, you are given N (1 <= N <= 100) guesses with their feedback in the middle of a game. You are asked to output the smallest four digit number which can be a candidate for codemaker's secret code (i.e., which satisfies all the constraints).

* Line 1: A single integer that is the smallest four-digit number (same range as the secret integer: 1000..9999) which could be the secret code. If there are no such numbers, output a single line containing the word "NONE" (without quotes).

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 412K, 提交时间: 2019-11-04 00:06:39

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int n;
string s[110];
int t1[110],t2[110];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i]>>t1[i]>>t2[i];
	int biao = 1;
	for(int i=1000;biao&&i<=9999;i++)
	{
		int ke = 1;
		string num="1000";
		num[0] = i/1000+'0';
		num[1] = i%1000/100+'0';
		num[2] = i%100/10+'0';
		num[3] = i%10+'0';
		for(int j=1;ke&&j<=n;j++)//数为i,第j种判断 
		{
			int vis1[4];
			int vis2[4];
			memset(vis1,0,sizeof(vis1));
			memset(vis2,0,sizeof(vis2));
			int dui = 0;
			int cuo = 0;
			for(int k=0;k<4;k++)
				if(s[j][k]==num[k])
				{
					dui++;
					vis1[k] = 1;
					vis2[k] = 1;
				}
			for(int k=0;k<4;k++)
				if(!vis1[k])
				{
					for(int L=0;L<4;L++)
					{
						if(vis2[L]) continue;
						if(num[k]!=s[j][L]) continue;
						vis2[L] = 1;
						cuo++;
						break;
					}
				}
			if(!(dui==t1[j]&&cuo==t2[j])) ke = 0;
		}
		if(ke)
		{
			biao = 0;
			cout<<i<<endl;
		}
	}
	if(biao) cout<<"NONE\n";
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 504K, 提交时间: 2019-11-04 11:00:52

#include<cstdio>
int min(int a,int b){return a<b?a:b;}
int n,N[105][4],ans1[105],ans2[105],cnt1[12],cnt2[12];
int main(){
	scanf("%d",&n);
	for(int i=1,x;i<=n;++i)scanf("%d%d%d",&x,&ans1[i],&ans2[i]),N[i][0]=x/1000,N[i][1]=x/100%10,N[i][2]=x/10%10,N[i][3]=x%10;
	for(int i=1000;i<=9999;++i){
		int num[4]={i/1000,i/100%10,i/10%10,i%10},ok=1;
		for(int p=1;p<=n;++p){
			int a1=0,a2=0;
			for(int j=0;j<4;++j)if(num[j]==N[p][j])a1++;else cnt1[num[j]]++,cnt2[N[p][j]]++;
			if(a1!=ans1[p]){ok=0;for(int i=0;i<10;++i)cnt1[i]=cnt2[i]=0;break;}
			for(int j=0;j<10;++j)a2+=min(cnt1[j],cnt2[j]),cnt1[j]=cnt2[j]=0;
			if(a2!=ans2[p]){ok=0;break;}
		}
		if(ok)return printf("%d\n",i),0;
	}puts("NONE");
}

详情