996
HDU1172 猜數字
猜數字Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2313 Accepted Submission(s): 1329
Problem Description
猜數字遊戲是gameboy最喜歡的遊戲之一。遊戲的規則是這樣的：計算機隨機產生一個四位數，然後玩家猜這個四位數是什麼。每猜一個數，計算機都會告訴玩家猜對幾個數字，其中有幾個數字在正確的位置上。
比如計算機隨機產生的數字為1122。如果玩家猜1234,因為1,2這兩個數字同時存在於這兩個數中，而且1在這兩個數中的位置是相同的，所以計算機會告訴玩家猜對了2個數字，其中一個在正確的位置。如果玩家猜1111,那麼計算機會告訴他猜對2個數字，有2個在正確的位置。
現在給你一段gameboy與計算機的對話過程，你的任務是根據這段對話確定這個四位數是什麼。
Input
輸入數據有多組。每組的第一行為一個正整數N(1<=N<=100)，表示在這段對話中共有N次問答。在接下來的N行中，每行三個整數A,B,C。gameboy猜這個四位數為A，然後計算機回答猜對了B個數字，其中C個在正確的位置上。當N=0時，輸入數據結束。
Output
每組輸入數據對應一行輸出。如果根據這段對話能確定這個四位數，則輸出這個四位數，若不能，則輸出"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
本題采用的是暴力搜索法，在1000至9999中尋找滿足已經給出的那些數的情況，看看是不是每一個都符合，如果有這樣的數且在1000到9999中隻有一個，那麼就是這個數，如果有多個，那麼這個數就是不確定的數
#include<stdio.h>
#include<string.h>
struct node
{
int number,lock,sum;
}per[150];
int Check(int n,int m)
{
int a[4],b[4],sign[4],i,j,sumn;
for(i=0;i<4;i++) sign[i]=0;
a[0]=n/1000;
a[1]=(n/100)%10;
a[2]=(n/10)%10;
a[3]=n%10;
b[0]=per[m].number/1000;
b[1]=(per[m].number/100)%10;
b[2]=(per[m].number/10)%10;
b[3]=per[m].number%10;
sumn=0;
for(i=0;i<4;i++)//判斷位置相同數
{
if(a[i]==b[i])
sumn++;
}
if(sumn!=per[m].lock) return 0;
sumn=0;
for(i=0;i<4;i++)//判斷數字相同數
{
for(j=0;j<4;j++)
{
if(a[i]==b[j]&&sign[j]==0)//Bug：隻能比較一次
{sumn++;sign[j]=1;break;}
}
}
if(sumn!=per[m].sum) return 0;
return 1;
}
int main()
{
int i,j,n,flag,Sum,num;
while(scanf("%d",&n),n!=0)
{
for(i=0;i<n;i++)
scanf("%d%d%d",&per[i].number,&per[i].sum,&per[i].lock);
flag=0;Sum=0;
for(i=1000;i<=9999;i++)
{
for(j=0;j<n;j++)
{
flag=Check(i,j);
if(!flag)break;
}
if(flag==1)
{Sum++;num=i;}
}
if(Sum==1)
printf("%d\n",num);
else
printf("Not sure\n");
memset(per,0,sizeof(per));
}
return 0;
}
最後更新：2017-04-03 12:54:51