一賽解題報告problem

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數(shù)字猜想數(shù)字猜想是一個電腦游戲。首先，電腦會選擇四個不重復(fù)的數(shù)字，你要根據(jù)電腦的提示盡快地猜出這個數(shù)字。電腦給的提示形式是“#A#B”，其中“#”是0

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

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;//鏈表結(jié)束標志}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;+