[読み込み]ACM HDU 1172数字当て(列挙法)

数字を当てる
Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 852    Accepted Submission(s): 481
Problem Description
デジタルゲームはgameboyが一番好きなゲームの一つです.ゲームのルールは、コンピュータがランダムに4桁を生成し、プレイヤーがこの4桁が何なのかを推測することです.1つの数を当てるたびに、コンピュータはプレイヤーにいくつかの数字を当てて、その中にいくつかの数字が正しい位置にあることを教えます.
例えば、コンピュータがランダムに生成した数字は1122である.プレイヤーが1234を当てると、1,2の2つの数字が同時にこの2つの数の中に存在し、1がこの2つの数の中で同じ位置にあるため、コンピュータはプレイヤーに2つの数字を当てて、そのうちの1つが正しい位置にあることを教えます.プレイヤーが1111を当てると、コンピュータは2つの数字を当てて、2つが正しい位置にあることを教えてくれます.
今gameboyとコンピュータの会話の過程をあげます.あなたの任務はこの会話に基づいてこの4桁が何なのかを確定することです.
 
Input
入力データは複数組あります.各グループの第1の行為には正の整数N(1<=N<=100)があり、この会話にはN回の問答があることを示している.次のN行では、各行に3つの整数A,B,Cがある.gameboyはこの4桁をAと推測し、コンピュータはBの数字を当てたと答え、そのうちCは正しい位置にある.N=0の場合、入力データは終了する.
 
Output
各入力データのセットは、1行の出力に対応します.この会話に基づいてこの4桁を特定できれば、この4桁を出力し、できなければ「Not sure」を出力します.
 
Sample Input
6 4815 2 1 5716 1 0 7842 1 0 4901 0 0 8585 3 3 8555 3 2 2 4815 0 0 2999 3 3 0
 
Sample Output
3585 Not sure
 
Author
lwg
 
 

#include<stdio.h>
bool check1(int num1,int num2,int t)
{
    int a[4],b[4];
    int c[4];
    int i,j;
    for(i=0;i<4;i++)
    {
        a[i]=num1%10;
        num1/=10;
        b[i]=num2%10;
        num2/=10;
        c[i]=0;
    }   
    int m=0;
    for(i=0;i<4;i++)
       for(j=0;j<4;j++)
          if(c[j]==0&&a[i]==b[j])
          {
              m++;
              c[j]=1;
              break;
          }    
    if(m==t)  return true;
    else return false;
}  
bool check2(int num1,int num2,int t)
{
    int a[4],b[4];
    int i,j;
    int m=0;
    for(i=0;i<4;i++)
    {
        a[i]=num1%10;
        num1/=10;
        b[i]=num2%10;
        num2/=10;
        if(a[i]==b[i]) m++;
    }   
    if(m==t)  return true;
    else  return false; 
}  
int main()
{
    int a[101],b[101],c[101];
    int cnt,res;
    int n,i,j;
    while(scanf("%d",&n),n)
    {
        for(i=0;i<n;i++)
           scanf("%d%d%d",&a[i],&b[i],&c[i]);
        cnt=0;
        for(i=1000;i<=9999;i++)
        {
            for(j=0;j<n;j++)
            {
                  if(check1(i,a[j],b[j])==false)break;
                  if(check2(i,a[j],c[j])==false)break;
            }  
            if(j>=n)
            {
                cnt++;
                res=i;
            } 
            if(cnt>=2)break;     
        }
        if(cnt==0||cnt>=2) printf("Not sure
");
        else printf("%d
",res);    
    }   
    return 0; 
}   

記事の出典:http://www.cnblogs.com/kuangbin/archive/2011/08/12/2136005.html