ZJNU 1205

双层枚举嫌疑犯与当日是星期几，统计真话与假话是否满足题意

注意 fake<=N&&fake+neutral>=N 即假话数量不大于N，假话加上没用的废话数量不小于N

（注意OJ上的数据存在问题：冒号后跟一个空格，CHARLES的话最后的句号‘.’应为半角，非全角）

可用样例输入：

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??

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Par;
typedef pair<int,Par> Pr;
int M,N,P,ans,f[25];
char s1[300],s2[300],s3[300];
string dayStr[7]={
    "Monday"
    ,"Tuesday"
    ,"Wednesday"
    ,"Thursday"
    ,"Friday"
    ,"Saturday"
    ,"Sunday"
};
vector<string> name;
map<string,int> mp;
Pr prd[105];
inline int readDigit(){
    int x=0;char c=getchar();
    while(!isdigit(c))c=getchar();
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    return x;
}
inline void readName(){
    char c;int i=0;
    while((c=getchar())!='
')s1[i++]=c;
    s1[i]='';
}
inline void readSubj(){
    char c;int i=0;
    while((c=getchar())!=' ')s2[i++]=c;
    s2[i-1]='';
}
inline void readWords(){
    char c;int i=0;
    while((c=getchar())!='
')s3[i++]=c;
    s3[i]='';
}
int main(){
    int i,j,day,gty,fake,neutral,subid;
    string sd;
    bool jd,prim;
    M=readDigit();
    N=readDigit();
    P=readDigit();
    for(i=0;i<M;i++){
        readName();
        name.push_back(s1);
        mp[s1]=i;
    }
    for(i=0;i<P;i++){
        readSubj();
        readWords();
        sd=s3;
        subid=mp[s2];
        if(sd=="I am guilty.")
            prd[i]=Pr(1,Par(subid,subid));
        else if(sd=="I am not guilty.")
            prd[i]=Pr(2,Par(subid,subid));
        else{
            jd=false;
            for(j=0;!jd&&j<7;j++)
                if(sd=="Today is "+dayStr[j]+"."){
                    prd[i]=Pr(3,Par(subid,j));
                    jd=true;
                    break;
                }
            for(j=0;!jd&&j<M;j++){
                if(sd==name[j]+" is guilty."){
                    prd[i]=Pr(1,Par(subid,j));
                    jd=true;
                    break;
                }
                else if(sd==name[j]+" is not guilty."){
                    prd[i]=Pr(2,Par(subid,j));
                    jd=true;
                    break;
                }
            }
            if(!jd)
                prd[i]=Pr(4,Par(0,0));
        }
    }
    for(jd=false,day=0;day<7;day++){
        for(gty=0;gty<M;gty++){
            memset(f,0,sizeof f);
            prim=true;
            for(i=0;i<P;i++){
                if(prd[i].first==1){
                    if(prd[i].second.second==gty){
                        if(!f[prd[i].second.first])
                            f[prd[i].second.first]=1;
                        else if(f[prd[i].second.first]==2){
                            prim=false;
                            break;
                        }
                    }
                    else{
                        if(!f[prd[i].second.first])
                            f[prd[i].second.first]=2;
                        else if(f[prd[i].second.first]==1){
                            prim=false;
                            break;
                        }
                    }
                }
                else if(prd[i].first==2){
                    if(prd[i].second.second!=gty){
                        if(!f[prd[i].second.first])
                            f[prd[i].second.first]=1;
                        else if(f[prd[i].second.first]==2){
                            prim=false;
                            break;
                        }
                    }
                    else{
                        if(!f[prd[i].second.first])
                            f[prd[i].second.first]=2;
                        else if(f[prd[i].second.first]==1){
                            prim=false;
                            break;
                        }
                    }
                }
                else if(prd[i].first==3){
                    if(prd[i].second.second==day){
                        if(!f[prd[i].second.first])
                            f[prd[i].second.first]=1;
                        else if(f[prd[i].second.first]==2){
                            prim=false;
                            break;
                        }
                    }
                    else{
                        if(!f[prd[i].second.first])
                            f[prd[i].second.first]=2;
                        else if(f[prd[i].second.first]==1){
                            prim=false;
                            break;
                        }
                    }
                }
            }
            if(!prim)
                continue;
            neutral=fake=0;
            for(i=0;i<M;i++)
                if(f[i]==0)
                    neutral++;
                else if(f[i]==2)
                    fake++;
            if(fake<=N&&fake+neutral>=N){
                if(!jd){
                    jd=true;
                    ans=gty;
                }
                else if(jd&&ans!=gty){
                    puts("Cannot Determine");
                    return 0;
                }
            }
        }
    }
    if(jd)
        puts(name[ans].data());
    else
        puts("Impossible");
    
    return 0;
}