The20084thHunanUniversityProgrammingContest

ProblemL

NumberGuessingLecture:WuHaoDate:2008/5/25DescriptionNumberGuessingisacomputergame.First,thecomputerchoosesfourdifferentdigits,youneedtoguessthesefourdigitsinthefewesttimes，foreachguess,thecomputerwillshowajudgementintheformof"#A#B","#"isanumber0~4."#A"showshowmanydigitsyouguessedwithbothcorrectvalueandposition."#B"showshowmanydigitsyouguessedwithcorrectvalue.Forexample,thecomputerchose1234,andyouguessed6139,thecomputerwillshow"1A2B"foryouhavenumber"1"correctvaluebutwrongpositionandnumber"3"correctvaluewithcorrectposition.Thusthecomputergivesyouthejudgementof"1A2B"Nowyouhavememorizedthedigitsyouguessedandthejudgementsyougot,youfeellikeyoucanfigureoutthecorrectanswer.Lifeisfilledwithwisdom,isn'tit?InputThereareseveraltestcases.Foreachtestcase,thefirstlinecontainsasinglepositiveintegerNindicatesthetimesyoucanguess，thefollowingNlinesistherecordoftheguess,intheform:#####A#BThefirstfournumbersisthenumbersguessed，thenthejudgementsforyourguess.OutputForeachtestcase,outputasinglelinecontainsexactlyfourdigitsthatthecomputerhaschosen.Youmayassumethateachtestcasegivesyouenoughinformation,soyoucanfigureoutthecorrectanswer.SampleInput212342A4B12430A4B307323A3B15260A0B45670A2B-1OutputforSampleinput21340734數字猜想數字猜想是一個電腦游戲。首先，電腦會選擇四個不重復的數字，你要根據電腦的提示盡快地猜出這個數字。電腦給的提示形式是“#A#B”，其中“#”是0

4的數字。其中“#A”表示猜中了數字.和位置的數目，“#B”表示猜中數字的數目。比如，電腦選擇的是1234，你猜的是6139，電腦給的提示是“1A2B”，因為數字“3”既猜中了數字，也猜對了位置，而數字“1”只猜中了數字，所以電腦給的提示就是“1A2B”。現在，你仔細記錄了你每次猜的數字和電腦的提示，你感覺應該可以猜對結果了。是的，生活中充滿了智慧，不是嗎？輸入有多個測試序列。每個測試序列的第一行是一個單獨的正整數N，表示猜想的次數，接下來的N行是N次猜想的記錄，形式為：#####A#B前面四個數字是猜想的數字，后面是電腦對猜想的提示。輸入N為0或者負整數表示輸入結束，并且無須處理。輸出對于每個測試序列，輸出一行，給出電腦選定的數字，要求數字和位置都正確。你可以假設，每個測試序列都提供了足夠的信息，讓你可以猜出該數字。輸入樣例212342A4B12430A4B307323A3B15260A0B45670A2B-1輸出樣例21340734解題報告本題采用蠻力搜索的方法可以解決。可能解的總數是10*9*8*7=5040。將這些可能的解與記錄的提示內容進行比較，保留和提示結果相同的解。直至最后只有一個唯一解為止。數據結構采用鏈表形式存儲所有可能解。對于每次猜測，從鏈表的第一個元素開始，和提示進行比對，如果和提示吻合，保留該元素，否則，去掉該元素。最后，鏈表中保留的唯一元素，也即鏈表的頭元素就是問題的解。標程(一)#include<stdio.h>#defineLoop(x)for(x=0;x<10;++x)#defineN5040//5040是解的總數chars[N][5];//s存儲所有可能解，和鏈表對應intf[N],head;//鏈表存儲結果，head是頭指針voidinit(){//初始化，得到所有可能解

inti,j,k,l,n=0;Loop(i)Loop(j)Loop(k)Loop(l)if(i!=j&&i!=k&&i!=l&&j!=k&&j!=l&&k!=l)sprintf(s[n++],"%d%d%d%d",i,j,k,l);}標程(二)intcheck(char*s1,char*s2,inta,intb){/*函數檢查猜測結果s1與可能的解s2是否吻合，a是猜對位置和數字的個數，b是只猜對數字的個數，如果吻合，返回1，否則0；*/inti,c,d[10];for(i=c=0;i<4;++i)if(s1[i]==s2[i])++c;if(c!=a)return0;Loop(i)d[i]=0;for(i=0;i<4;++i)d[s1[i]-'0']++;for(i=c=0;i<4;++i)d[s2[i]-'0']++;Loop(i)if(d[i]==2)c++;if(c!=b)return0;return1;}標程(三)voidjudge(char*ss,inta,intb){//對于猜測ss及結果，把不符合條件的元素去掉

inti,j;while(!check(ss,s[head],a,b))head=f[head];//尋找頭指針

for(i=head,j=f[i];j<N;j=f[j])if(check(ss,s[j],a,b))i=f[i]=j;//后繼元素

f[i]=N;//鏈表結束標志}intmain(){inti,n,a,b;chars1[5],s2[5];

init();while(scanf("%d",&n),n>0){for(i=0;i<N;++i)f[i]=i+1;head=0;//鏈表初始化

for(i=0;i<n;+