CF-63C Bulls and Cows游戏如何通过枚举策略提高猜数准确率？

本文共计978个文字，预计阅读时间需要4分钟。

C+-Bulls+and+Cows+时间限制：2000MS内存限制：262144KB64位IO格式：%I64d +%I64uSubmit+Status+Practice+CodeForces+63C+Description+Bulls+and+Cows+游戏需要两个人玩，一个人出题，另一个人猜答案。游戏的目标是通过每次猜谜结果，逐渐缩小可能的答案范围，最终猜出正确的数字。

C -Bulls and Cows

Time Limit:2000MSMemory Limit:262144KB64bit IO Format:%I64d & %I64u

​​Submit​​​ ​​​Status​​​ ​​​Practice​​​ ​​​CodeForces 63C​​

Description

The "Bulls and Cows" game needs two people to play. The thinker thinks of a number and the guesser tries to guess it.

The thinker thinks of a four-digit number in the decimal system. All the digits in the number are different and the number may have a leading zero. It can't have more than one leading zero, because all it's digits should be different. The guesser tries to guess the number. He makes a series of guesses, trying experimental numbers and receives answers from the first person in the format "xbullsycows".xrepresents the number of digits in the experimental number that occupy the same positions as in the sought number.y

For example, let's suppose that the thinker thought of the number0123. Then the guessers' experimental number1263will receive a reply "1 bull 2 cows" (3 occupies the same positions in both numbers and 1 and 2 are present in both numbers but they occupy different positions). Also, the answer to number8103

When the guesser is answered "4 bulls 0 cows", the game is over.

Now the guesser has already made several guesses and wants to know whether his next guess can possibly be the last one.

Input

The first input line contains an integern(1 ≤ n ≤ 10) which represents the number of already made guesses. Then follownlines in the form of "a_ib_ic_i", wherea_iis thei-th experimental number,b_iis the number of bulls,c_iis the number of cows (1 ≤ i ≤ n,0 ≤ b_i, c_i, b_i + c_i ≤ 4). The experimental numbers are correct, i.e., each of them contains exactly four digits, in each of them all the four digits are different, and there can be a leading zero. All the experimental numbers are different. As the guesser hasn't guessed the number yet, the answer "4 bulls 0 cows" is not present.

Output

If the input data is enough to determine the sought number, print the number with four digits on a single line. If it has less than four digits, add leading zero. If the data is not enough, print "Need more data" without the quotes. If the thinker happens to have made a mistake in his replies, print "Incorrect data" without the quotes.

Sample Input

Input

21263 1 28103 2 1

Output

Need more data

Input

21234 2 21256 0 2

Output

2134

Input

20123 1 14567 1 2

Output

Incorrect data

思路：枚举0-9999，看符合条件的数有几个，没有说明信息有误，一个，答案唯一，多个，需要更多信息

#include<iostream>#include<cstring>#include<cstdio>using namespace std;class node{ public:int a,b,c;}f[111];int n;int main(){ while(cin>>n) { for(int i=0;i<n;++i) { cin>>f[i].a>>f[i].b>>f[i].c; } int ans=0,kkans; int a,b,c,d,z,bb,cc,zz; for(int i=0;i<10000;++i) { z=i;a=z%10;z/=10;b=z%10;z/=10;c=z%10;z/=10;d=z%10; if(a==b||a==c||a==d||b==c||b==d||c==d)continue; bool yes=1; for(int j=0;j<n;++j) { bb=0;cc=0; z=f[j].a; zz=z%10; if(a==zz)bb++;if(b==zz)cc++;if(c==zz)cc++;if(d==zz)cc++; z/=10;zz=z%10; if(b==zz)bb++;if(a==zz)cc++;if(c==zz)cc++;if(d==zz)cc++; z/=10;zz=z%10; if(c==zz)bb++;if(a==zz)cc++;if(b==zz)cc++;if(d==zz)cc++; z/=10;zz=z%10; if(d==zz)bb++;if(a==zz)cc++;if(b==zz)cc++;if(c==zz)cc++; if(bb!=f[j].b||cc!=f[j].c){yes=0;break;} } if(yes){ans++;kkans=i;} } if(ans==0)cout<<"Incorrect data\n"; else if(ans==1)printf("%04d\n",kkans); else cout<<"Need more data\n"; }}