记录编号 | 124531 | 评测结果 | AAAAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [NOIP 2003]侦探推理 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 0.005 s | ||
提交时间 | 2014-10-04 15:52:08 | 内存使用 | 0.32 MiB | ||
#include <cstdio> #include <cstring> struct plot {int k,n;}p[30][110],tmp; // k==1 -> is guilty; k==2 -> isn't guilty; k==3 -> today is XXX int M,N,P,i,s[30],sub,ans; char nm[30][260],str[260],name[260],name2[260]; bool f[30]; int check() { int i,j,g[30],d[10],cnt=0,cri; plot tmp; memset(g,-1,sizeof(g)); memset(d,-1,sizeof(d)); for (i=1;i<=M;++i) for (j=1;j<=s[i];++j) { tmp=p[i][j]; if (!f[i]&&tmp.k==1) tmp.k=2; else if (!f[i]&&tmp.k==2) tmp.k=1; else if (!f[i]&&tmp.k==3) tmp.k=4; else if (!f[i]&&tmp.k==4) tmp.k=3; switch (tmp.k) { case 1: if (g[tmp.n]==-1) g[tmp.n]=1; else if (g[tmp.n]==0) return 0; break; case 2: if (g[tmp.n]==-1) g[tmp.n]=0; else if (g[tmp.n]==1) return 0; break; case 3: if (d[tmp.n]==-1) d[tmp.n]=1; else if (d[tmp.n]==0) return 0; break; case 4: if (d[tmp.n]==-1) d[tmp.n]=0; else if (d[tmp.n]==1) return 0; } } for (i=1;i<=7;++i) if (d[i]==1) ++cnt; if (cnt>1) return 0; cnt=0; for (i=1;i<=M;++i) if (g[i]==1) {++cnt; cri=i;} if (cnt==1) return cri; if (cnt>1) return 0; cnt=0; for (i=1;i<=M;++i) if (g[i]==-1) {++cnt; cri=i;} if (cnt==1) return cri; if (cnt>1) return -1; return 0; } void dfs(int dep,int tot) { if (dep>M) { if (tot<=N) return; //for (int i=1;i<=M;++i) putchar(48+f[i]); putchar('\n'); int tmp=check(); //printf("%d\n",tmp); if (tmp&&!ans) ans=tmp; else if (tmp>0&&ans>0&&ans!=tmp) ans=-1; return; } f[dep]=1; dfs(dep+1,tot); if (tot<=N) {f[dep]=0; dfs(dep+1,tot+1);} } int main() { freopen("logic.in","r",stdin); freopen("logic.out","w",stdout); scanf("%d%d%d",&M,&N,&P); for (i=1;i<=M;++i) scanf("%s",nm[i]); while (P--) { tmp=(plot){0,0}; scanf("%s%s",name,name2); name[strlen(name)-1]='\0'; for (i=1;i<=M;++i) if (strcmp(name,nm[i])==0) sub=i; fgets(str,sizeof(str),stdin); if (str[strlen(str)-1]=='\n') str[strlen(str)-1]='\0'; if (strcmp(str," am guilty.")==0) {if (strcmp(name2,"I")==0) tmp=(plot){1,sub};} else if (strcmp(str," am not guilty.")==0) {if (strcmp(name2,"I")==0) tmp=(plot){2,sub};} else if (strcmp(str," is guilty.")==0) {for (i=1;i<=M;++i) if (strcmp(name2,nm[i])==0) tmp=(plot){1,i};} else if (strcmp(str," is not guilty.")==0) {for (i=1;i<=M;++i) if (strcmp(name2,nm[i])==0) tmp=(plot){2,i};} else if (strcmp(str," is Monday.")==0) {if (strcmp(name2,"Today")==0) tmp=(plot){3,1};} else if (strcmp(str," is Tuesday.")==0) {if (strcmp(name2,"Today")==0) tmp=(plot){3,2};} else if (strcmp(str," is Wednesday.")==0) {if (strcmp(name2,"Today")==0) tmp=(plot){3,3};} else if (strcmp(str," is Thursday.")==0) {if (strcmp(name2,"Today")==0) tmp=(plot){3,4};} else if (strcmp(str," is Friday.")==0) {if (strcmp(name2,"Today")==0) tmp=(plot){3,5};} else if (strcmp(str," is Saturday.")==0) {if (strcmp(name2,"Today")==0) tmp=(plot){3,6};} else if (strcmp(str," is Sunday.")==0) {if (strcmp(name2,"Today")==0) tmp=(plot){3,7};} p[sub][++s[sub]]=tmp; //printf("sub=%d type=%d num=%d\n",sub,tmp.k,tmp.n); } dfs(1,1); if (ans==-1) printf("Cannot Determine\n"); else if (ans==0) printf("Impossible\n"); else printf("%s\n",nm[ans]); fclose(stdin); fclose(stdout); return 0; }