题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：
证词中出现的其他话，都不列入逻辑推理的内容。
明明所知道的是，他的同学中有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
惊天大模拟
惊天码农题
首先需要花式截取出每个人的信息，然后需要记录以下信息：
每个人说的日期
每个人说自己是不是罪犯
每个人说谁是罪犯
每个人说谁不是罪犯
枚举日期和嫌疑犯，进行判断：
记说谎人数为tmp，可疑人数为cnt（可疑人数指没有说过真话，也没有说过假话的人数），题目限制说谎人数为m
若tmp>m，说明当前枚举的情况不成立。
若tmp+cnt<m，说明已知说谎的人和可能说谎的人加起来都不够目标值，不成立。
除此之外的情况下，当前枚举到的嫌疑犯可能是罪犯。
若可能是罪犯的人数大于1人，cannot determine
/*By SilverN*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
string pp[]={"am guilty","am not guilty","is guilty.","is not guilty."};
string week[]={" ","is Monday","is Tuesday","is Wednesday","is Thursday","is Friday","is Saturday","is Sunday"};
//
int n,m,p;
//
string name[];
map<string,int>mp;
//人名
string s[];
struct person{
bool is;//是否确定是罪犯
int wk;//每个人对天气的判断
int guil[];//每个人对其他人身份的判断
vector<int>g_list,nog_list;//每个人指认的罪犯
}a[];
//身份信息
bool posi[];
int work(int day,int uso){
int cnt=,tmp=;//不确定的人，确定的凶手 for(int i=;i<=n;i++){
bool f_true=,f_false=;
if(a[i].is || (a[i].wk && a[i].wk!=day)){//天气说错
f_false=;
}
if(a[i].guil[uso]==-){//说罪犯不是罪犯
f_false=;
}
if(a[i].guil[uso]==)f_true=;//说罪犯是罪犯
if(i!=uso && a[i].guil[i]==){//不是罪犯说自己是罪犯
f_false=;
}
for(int j=;j<a[i].g_list.size();j++)if(a[i].g_list[j]!=uso){//说不是罪犯的人是罪犯
f_false=;
}
for(int j=;j<a[i].nog_list.size();j++)if(a[i].nog_list[j]!=uso){//说不是罪犯的人不是罪犯
f_true=;
}
if(a[i].wk==day)f_true=;
if(i==uso && a[i].guil[uso]==) f_true=;//凶手说自己是凶手
if(i!=uso && a[i].guil[i]==-) f_true=;//不是凶手说自己不是凶手
if(f_true && f_false)return ;//不合法
if(f_false)tmp++;
if(!f_true && !f_false)cnt++;//不确定的人
}
// printf("day:%d uso:%d cnt:%d tmp:%d\n",day,uso,cnt,tmp); if(tmp>m)return ;
if(tmp+cnt<m)return ;
return ;
}
int target=;
void solve(){
int tmp=;
int i,j;
for(i=;i<=;i++)//枚举日期
for(j=;j<=n;j++)//枚举凶手
{
if(posi[j])continue;
if(work(i,j)){
++tmp;
posi[j]=;
if(tmp>=){
printf("Cannot Determine\n");
return;
}
target=j;
}
}
if(!target)printf("Impossible\n");
cout<<name[target]<<endl;
return;
}
//
int main(){
scanf("%d%d%d",&n,&m,&p);//总人数 说谎人数 证言数
int i,j;
for(i=;i<=n;i++){
cin>>name[i];
mp[name[i]]=i;
}
for(i=;i<=p;++i){
cin>>s[i];
// cout<<"test"<<s[i]<<endl;
s[i]=s[i].substr(,s[i].find(':'));
// cout<<"finn"<<endl;
int id=mp[s[i]];
getchar();
getline(cin,s[i]);
// cout<<"now-"<<s[i]<<endl;
//判断
if(s[i][]=='I'){
if(s[i].find(pp[])!=-){//I am guilty
a[id].guil[id]=; continue;
}
else if(s[i].find(pp[])!=-){//I am not guilty
a[id].guil[id]=-; continue;
}
}
else{
int tmp=;
tmp=s[i].find(pp[]);
if(tmp!=-){//is guilty
// printf("is guilty: %d\n",tmp);
s[i]=s[i].substr(,tmp-);
// printf("mp:%d\n",mp[s[i]]);
// cout<<"test: "<<s[i]<<"eld"<<endl;
a[id].guil[mp[s[i]]]=;
a[id].g_list.push_back(mp[s[i]]);
continue;
}
tmp=s[i].find(pp[]);
if(tmp!=-){//is not guilty
s[i]=s[i].substr(,tmp-);
// printf("mp:%d\n",mp[s[i]]);
// cout<<"test: "<<s[i]<<"eld"<<endl;
a[id].guil[mp[s[i]]]=-;
a[id].nog_list.push_back(mp[s[i]]);
continue;
}
for(j=;j<=;j++)//天气判定
{
tmp=s[i].find(week[j]);
if(tmp!=-){
if(!a[id].wk)
a[id].wk=j;
else a[id].is=;//天气前后矛盾，肯定是骗子
break;
}
}
}
//
}
//结束读入
/*
for(i=1;i<=n;i++){
printf("info of %d:\n",i);
cout<<name[i]<<endl; printf("wk: %d\n",a[i].wk);
printf("self: %d\n",a[i].guil[i]);
for(j=0;j<a[i].g_list.size();j++)printf("%d ",a[i].g_list[j]);
printf("\n");
for(j=0;j<a[i].nog_list.size();j++)printf("%d ",a[i].nog_list[j]);
printf("\n");
}*/
//
solve(); return ;
}