noip2003侦探推理

noip2003·侦探推理·字符串处理·逻辑判断

【问题描述】
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：

证词中出现的其他话，都不列入逻辑推理的内容。
明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。
现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！

【输入格式】
输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；
M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，
每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。
往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。
输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。

【输出格式】
如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是
罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。

【输入样例】
3 1 5
MIKE
CHARLES
KATE
MIKE:I am guilty.
MIKE:Today is Sunday.
CHARLES:MIKE is guilty．
KATE:I am guilty.
KATE:How are you??

【输出样例】
MIKE
...............................................................................................
注意两点：
1.不要按照每句话来分析，枚举答案要方便得多，枚举当前日期，谁是罪犯，然后判断句子真假；这样每句话的真假是确定的——有点二分答案的味道！判断出的真话数不大于总人数减去给定假话人数，判断出的假话人数不大于给定假话人数，用不大于是因为有人不说话！
2.字符串处理：判断话是谁说的不能简单在句子中定位人名，也不能定位人名+':'，因为会有这种情况：
A:……,AA:……,这样两种方法都不行了，只能找到冒号，比较第一位到冒号之前是否等于某个人名！同样有人名叫FRIDAY但这并不影响，幸好人名大写！同样定位某人说的话中的主语，要定位人名+' ',防止与说话人名字重复！
可能我的代码还有bugs，但数据全过了。
My code(第一次）:
const day:array[1..7]of string=('Monday','Tuesday','Wednesday','Thursday','Friday','Saturday','Sunday');
var man:array[0..30]of string;
lie:array[0..30]of longint;
guilty,today,lienu,honest:longint;
i,j,k,l,m,n,p:longint;
words:array[0..100]of string;
ans,flag:longint;
procedure init;
var i:longint;
begin
readln(n,m,p);
for i:=1 to n do
readln(man[i]);
for i:=1 to p do
readln(words[i]);
end;
function findbody(s:string):longint;
var i,j:longint;
begin
for i:=1 to n do
begin
j:=pos(':',s);
if copy(s,1,j-1)=man[i] then exit(i);
end;
exit(0);
end;
function findsub(s:string):longint;
var i:longint;
begin
for i:=1 to n do
if pos(man[i]+' ',s)=1 then exit(i);
exit(0);
end;
function findday(s:string):longint;
var i:longint;
begin
for i:=1 to 7 do
if pos(day[i],s)<>0 then exit(i);
exit(0);
end;
procedure go;
var i,j,k,l,k1,k2:longint;
s:string;
begin
for i:=1 to n do lie[i]:=-1;
lienu:=0; honest:=0;
for i:=1 to p do
begin
k:=findbody(words[i]);
if pos('I am guilty.',words[i])<>0 then
begin
k1:=1;k2:=k;
end else
if pos('I am not guilty.',words[i])<>0 then
begin
k1:=2;k2:=k;
end else
if pos('is guilty.',words[i])<>0 then
begin
s:=words[i];delete(s,1,length(man[k]));
if s[1]=' 'then delete(s,1,1);
if s[1]=':' then delete(s,1,1);
if s[1]=' ' then delete(s,1,1);
k1:=3;k2:=findsub(s);
end else
if pos('is not guilty.',words[i]) <>0 then
begin
s:=words[i];delete(s,1,length(man[k]));
if s[1]=' 'then delete(s,1,1);
if s[1]=':' then delete(s,1,1);
if s[1]=' ' then delete(s,1,1);
k1:=4;k2:=findsub(s);
end else
if pos('Today is ',words[i])<>0 then
begin
l:=findday(words[i]);
k1:=5;k2:=l;
end else continue;
if (k1=1)and(k2<>guilty) or(k1=2)and(k2=guilty) or(k1=3)and(k2<>guilty)
or (k1=4)and(k2=guilty) or(k1=5)and(today<>k2) then
begin
if lie[k]=-1 then
begin
inc(lienu);lie[k]:=0;
end else
if lie[k]=1 then
begin
exit;
end;
end else
if (k1=1)and(k2=guilty) or(k1=2)and(k2<>guilty) or(k1=3)and(k2=guilty)
or (k1=4)and(k2<>guilty) or(k1=5)and(today=k2) then
begin
if lie[k]=0 then exit;
if lie[k]=-1 then begin lie[k]:=1; inc(honest);end;
end;
if lienu>m then exit;
end;
if lienu>m then exit;
if honest>n-m then exit;
if guilty<>ans then inc(flag);
ans:=guilty;
end;
begin
assign(input,'2.in');reset(input);
assign(output,'2.out');rewrite(output);
init;
flag:=0;
for guilty:=1 to n do
begin
for today :=1 to 7 do
begin
go;
if flag>=2 then break;
end;
if flag>=2 then break;
end;
if flag>=2 then writeln('Cannot Determine')else
if flag =1 then writeln(man[ans]) else
writeln('Impossible');
close(input);
close(output);
end.
My code(第二次）:
注：精简了一下找body，day的函数。
const day:array[1..7]of string=('Monday','Tuesday','Wednesday','Thursday','Friday','Saturday','Sunday');
var nam:array[0..30]of string;
lie:array[0..30]of longint;
flag,lienu,honest,n,m,p,i,j,k,l,today,guilty,ans:longint;
words:array[0..100]of string;
function findday(var s:string):longint;
var i:longint;
begin
for i:=1 to 7 do
if pos(day[i],s)<>0 then exit(i);
exit(0);
end;
function findbody(var s:string):longint;
var i,j:longint;
begin
j:=pos(':',s);
for i:=1 to n do
if (nam[i]=copy(s,1,j-1)) then
exit(i);
exit(0);
end;
function findgui(var s:string):longint;
var i:longint;
begin
for i:=1 to n do
if (pos(': '+nam[i]+' ',s)<>0)or(pos(':'+nam[i]+' ',s)<>0) then
exit(i);
exit(0);
end;
procedure go;
var k1,k2,i,j,k,l:longint;
s:string;
begin
lienu:=0;honest:=0;
for i:=1 to n do lie[i]:=-1;
for i:=1 to p do
begin
s:=words[i];
k:=findbody(s);
if pos('I am guilty.',s)<>0 then
begin
k1:=1;k2:=k;
end else
if pos('I am not guilty.',s)<>0 then
begin
k1:=2;k2:=k;
end else
if pos(' is guilty.',s)<>0 then
begin
k1:=3;k2:=findgui(s);
end else
if pos(' is not guilty.',s)<>0 then
begin
k1:=4;k2:=findgui(s);
end else
if pos('Today is ',s)<>0 then
begin
k1:=5;k2:=findday(s);
end else continue;
if (k1=1)and(k2<>guilty)or(k1=2)and(k2=guilty)or(k1=3)and(k2<>guilty)
or (k1=4)and(k2=guilty)or(k1=5)and(k2<>today) then
begin
if lie[k]=-1 then
begin
inc(lienu);
lie[k]:=0;
end else
if lie[k]=1 then
exit;
end else
if (k1=1)and(k2=guilty)or(k1=2)and(k2<>guilty)or(k1=3)and(k2=guilty)
or(k1=4)and(k2<>guilty)or(k1=5)and(k2=today) then
begin
if lie[k]=-1 then
begin
inc(honest);
lie[k]:=1;
end else
if lie[k]=0 then
exit;
end;
end;
if (lienu>m)or(honest>n-m) then exit;
if ans<>guilty then
begin
inc(flag);
ans:=guilty;
end
end;
begin
assign(input,'logic.in');reset(input);
assign(output,'logic.out');rewrite(output);
readln(n,m,p);
for i:=1 to n do
readln(nam[i]);
for i:=1 to p do
readln(words[i]);
flag:=0;
for guilty:=1 to n do
for today :=1 to 7 do
go;
if flag>=2 then writeln('Cannot Determine')else
if flag=0 then writeln('Impossible')else
writeln(nam[ans]);
close(input);
close(output);
end.

　　program NOIP2003_2_Logic;
　　const
　　maxm=20;
　　dow:array[1..7]of string=('Sunday.','Monday.','Tuesday.','Wednesday.',
　　'Thursday.','Friday.','Saturday.');
　　var
　　i,j,k,weekday,m,n,p,p1,p2,p3,index,resolution,total1,total2:byte;
　　name:array[1..maxm]of string;{存放人名}
　　witness10,witness20:array[1..100]of byte;{存放说话人的序号,分为两类,前者存放不含星期的证词的说话人的序号,后者存放只含星期的证词的说话人的序号}
　　witness1,witness2:array[1..100]of string;{存放证词,分为两类,第一类是不含星期的证词,第二类是只含星期的证词}
　　name0,temp,temp0,temp1,temp2:string;
　　truth,truth0:array[1..maxm]of byte; {存放诚信记录}
　　f1,f2:text;fn1,fn2,fileNo:string;
　　flag:boolean;
　　begin
　　write('Input fileNo:');readln(fileNo);
　　fn1:='logic.in'+fileNo;fn2:='logic.ou'+fileNo;
　　assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2);
　　readln(f1,m,n,p);
　　for i:=1 to m do readln(f1,name[i]);
　　total1:=0;total2:=0;
　　for i:=1 to p do begin{对证词预处理}
　　readln(f1,temp);
　　index:=pos(': ',temp);
　　temp1:=copy(temp,1,index-1);{取得说话人姓名}
　　temp2:=copy(temp,index+2,length(temp)-index-1);{取得证词}
　　if (temp2='I am guilty.') or (temp2='I am not guilty.') then
　　for j:=1 to m do
　　if name[j]=temp1 then begin
　　inc(total1);{total1表示第一类证词的总数}
　　witness10[total1]:=j;{记下第一类第total1条证词的说话人的序号}
　　witness1[total1]:=temp2;{记下第一类第total1条证词}
　　break;
　　end;
　　if (pos(' is guilty.',temp2)>0) or (pos(' is not guilty.',temp2)>0) then begin
　　temp0:=copy(temp2,1,pos(' is ',temp2)-1);{取得证词的叙述对象(主语)}
　　flag:=false;
　　for k:=1 to m do
　　if temp0=name[k] then begin
　　flag:=true;
　　break;
　　end;
　　if flag then{如果证词的叙述对象(主语)确实存在}
　　for j:=1 to m do
　　if name[j]=temp1 then begin{记入到第一类证词中}
　　inc(total1);
　　witness10[total1]:=j;
　　witness1[total1]:=temp2;
　　break;
　　end;
　　end;
　　flag:=false;
　　for j:=1 to 7 do
　　if temp2='Today is '+ dow[j] then begin
　　flag:=true;
　　break;
　　end;
　　if flag then{如果证词是关于星期的判断}
　　for j:=1 to m do
　　if name[j]=temp1 then begin{记入到第二类证词中}
　　inc(total2);{total2表示第二类证词的总数}
　　witness20[total2]:=j;{记下第二类第total2条证词的说话人的序号}
　　witness2[total2]:=temp2;{记下第二类第total2条证词}
　　break;
　　end;
　　end;
　　close(f1);
　　resolution:=0;{resolution表示解的个数 }
　　for i:=1 to m do begin{穷举,第i个人为罪犯}
　　if resolution>1 then break;{如果解的个数多于1个,则跳出循环}
　　fillchar(truth,sizeof(truth),0);{诚信记录赋初值为0,表示此人尚无有效证词}
　　for j:=1 to total1 do begin{逐条处理第一类证词}
　　if witness1[j]='I am guilty.' then begin{如果证词为I am guilty.}
　　if i=witness10[j] then{如果说话人就是罪犯,则本证词为真}
　　case truth[i] of
　　0:truth[i]:=1;{如果此人的诚信记录为0,则此人说真话(记为1)}
　　2:truth[i]:=3;{如果此人的诚信记录为2(即以前说假话),则此人自相矛盾(记为3)}
　　end
　　else{如果说话人不是罪犯,则本证词为假}
　　case truth[witness10[j]] of
　　0:truth[witness10[j]]:=2;{如果此人的诚信记录为0,则此人说假话(记为2)}
　　1:truth[witness10[j]]:=3;{如果此人的诚信记录为1(即以前说真话),则此人自相矛盾(记为3)}
　　end;
　　end;
　　if witness1[j]='I am not guilty.' then begin{如果证词为I am not guilty.}
　　if i=witness10[j] then{如果说话人是罪犯,则本证词为假}
　　case truth[i] of
　　0:truth[i]:=2;
　　1:truth[i]:=3;
　　end
　　else{如果说话人不是罪犯,则本证词为真}
　　case truth[witness10[j]] of
　　0:truth[witness10[j]]:=1;
　　2:truth[witness10[j]]:=3;
　　end;
　　end;
　　if (pos(' is guilty.',witness1[j])>0) then begin{如果证词含有is guilty. }
　　temp:=copy(witness1[j],1,pos(' is guilty.',witness1[j])-1);{取得证词的主语}
　　if name[i]=temp then{如果证词的主语是罪犯,则本证词为真}
　　case truth[witness10[j]] of
　　0:truth[witness10[j]]:=1;
　　2:truth[witness10[j]]:=3;
　　end
　　else{如果证词的主语不是罪犯,则本证词为假}
　　case truth[witness10[j]] of
　　0:truth[witness10[j]]:=2;
　　1:truth[witness10[j]]:=3;
　　end;
　　end;
　　if (pos(' is not guilty.',witness1[j])>0) then begin{如果证词含有is not guilty. }
　　temp:=copy(witness1[j],1,pos(' is not guilty.',witness1[j])-1);{取得证词的主语}
　　if name[i]=temp then{如果证词的主语是罪犯,则本证词为假}
　　case truth[witness10[j]] of
　　0:truth[witness10[j]]:=2;
　　1:truth[witness10[j]]:=3;
　　end
　　else{如果证词的主语不是罪犯,则本证词为真}
　　case truth[witness10[j]] of
　　0:truth[witness10[j]]:=1;
　　2:truth[witness10[j]]:=3;
　　end;
　　end;
　　end;{第一类证词全部处理完毕}
　　if total2>0 then begin{如果有第二类证词存在,处理第二类证词}
　　for k:=1 to m do truth0[k]:=truth[k];{记下第一类证词全部处理完毕后的诚信记录}
　　for weekday:=1 to 7 do begin{穷举,今天是星期日,星期一直到星期六}
　　for k:=1 to m do truth[k]:=truth0[k];{诚信记录还原为第一类证词全部处理完毕后的诚信记录}
　　for j:=1 to total2 do{逐条处理第二类证词}
　　if pos(dow[weekday],witness2[j])>0 then{如果证词中含有当前穷举的星期值,则本证词为真}
　　case truth[witness20[j]] of
　　0:truth[witness20[j]]:=1;
　　2:truth[witness20[j]]:=3;
　　end
　　else{如果证词中不含有当前穷举的星期值,则本证词为假}
　　case truth[witness20[j]] of
　　0:truth[witness20[j]]:=2;
　　1:truth[witness20[j]]:=3;
　　end;
　　p1:=0;p2:=0;p3:=0;
　　for k:=1 to m do if truth[k]=1 then inc(p1);{p1表示始终说真话的人的总数}
　　for k:=1 to m do if truth[k]=2 then inc(p2);{p2表示始终说假话的人的总数}
　　for k:=1 to m do if truth[k]=3 then inc(p3);{p3表示说过自相矛盾的话的人的总数}
　　if (p1<=m-n) and (p2<=n) and (p3=0) then begin{如果说真话的人的总数小于等于m-n且说假话的人的总数小于等于n且没有人说过自相矛盾的话,那么当前罪犯i就是本题的一个解}
　　name0:=name[i];{记下罪犯的姓名}
　　inc(resolution);{解的个数增1}
　　break;{退出星期的穷举}
　　end;
　　end;{星期的穷举完毕}
　　end;{第二类证词处理完毕}
　　p1:=0;p2:=0;p3:=0;
　　for k:=1 to m do if truth[k]=1 then inc(p1);
　　for k:=1 to m do if truth[k]=2 then inc(p2);
　　for k:=1 to m do if truth[k]=3 then inc(p3);
　　if (p1<=m-n) and (p2<=n) and (p3=0) and (name0<>name[i]) then begin{为避免重复计解,此处多加了一个条件: name0<>name[i]}
　　name0:=name[i];
　　inc(resolution);
　　end;
　　end;
　　if resolution=1 then writeln(f2,name0);{如果只有一个解,则输出罪犯姓名}
　　if resolution=0 then writeln(f2,'Impossible');{如果无解,则输出Impossible}
　　if resolution>1 then writeln(f2,'Cannot Determine');{如果有多个可能解,则输出Cannot Determine }
　　close(f2);
　　end.

挺漂亮，快乐分享大家，不论遇到什么事情，乐观，坚强，才是生活。祝大家开心每一天，，，，记得采纳哟，，，，