一赛解题报告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数字猜想数字猜想是一个电脑游戏。首先，电脑会选择四个不重复的数字，你要根据电脑的提示尽快地猜出这个数字。电脑给的提示形式是“#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;+