Detective reasoning
Title Description
Mingming's classmate has been fascinated by detective comics recently 《 Conan 》 And indulge in the reasoning game , So he called a group of students to play reasoning games . The content of the game is like this , Mingming's classmates first agreed to let one of them act as a criminal （ Without knowing it ）, Ming Ming's task is to find the criminal . next , Ask each student one by one , The interviewee may say ：
Content of testimony ：
I am guilty.
I am not guilty.
XXX is guilty.
XXX is not guilty.
Today is XXX
Meaning of testimony ：
I'm a criminal
I'm not a criminal
xxx It's a criminal （ xxx Indicates the name of a classmate ）
xxx Not a criminal
Today is xxx （ xxx Indicates the day of the week , yes Monday Tuesday wednesday Thursday Fnday Saturday One of ）
Other words in the testimony , Are not included in the content of logical reasoning . All I know is , Among his classmates N
Individuals always lie , The rest of us always tell the truth . Now? , Mingming needs your help to infer who the real killer is from his classmates' words , please remember , There's only one killer !
Enter description
Enter several lines .
The first line has three integers ,M（1 ≤ M ≤ 20）,N（1 ≤ N ≤ M） and P（1 ≤ P ≤ 100）;M Is the number of students who participated in the game ,N
Is the number of people who always lie ,P Is the total number of testimonies .
next M that 's ok , Each line is clearly the name of a classmate （ Composition of English letters , No nominative , All uppercase ）.
In the future P that 's ok , Each line begins with the name of a classmate , Followed by a colon and a space , Followed by a statement , Conform to the format listed in the previous table . Each line of testimony will not exceed 250 Characters .
Two consecutive spaces will not appear in the input , And there are no spaces at the beginning and end of each line .
Output description
If your program can determine who is the criminal , Then output his name ; If the program determines that more than one person may be a criminal , Then output Cannot
Determine; If the program determines that no one is likely to be a criminal , Then output Impossible.
Sample input and output
input
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??
output
MIKE
Operational limits
Maximum running time ：1s
Maximum running memory ：128M
/* Large scale simulation problem */ #include <bits/stdc++.h> using namespace std; //m： Total number n： Number of people who always lie
p： Total number of speakers int m, n, p; //judge[i]： The first i Is that true or false , really 1 false -1 unclear 0 w[i]： The first i What's the number of the bureau int
judge[21], w[200]; //err： Contradiction mark nx： Current potential criminals int err, nx; //name[i]： Everyone's name （ Number is 1~m）
say[i]： What everyone said day[i]： All day of week names string name[100], say[200]; string day[10] = {"0",
"Today is Sunday.", "Today is Monday.", "Today is Tuesday.", "Today is
Wednesday.", "Today is Thursday.", "Today is Friday.", "Today is Saturday.", };
//sset Function to mark whether a person speaks true or false void sset(int who, int x) { if (judge[who] == -x) err = 1;
// If a person tells the truth and lies , Then contradiction else judge[who] = x; } int main() { cin >> m >> n >> p; for
(int i = 1; i <= m; i++) { cin >> name[i]; } for (int i = 1; i <= p; i++) {
string nm; cin >> nm; // Enter the name of the person who said this sentence nm.erase(nm.end() - 1);
// delete nm Middle colon , It's easy to judge the number of this sentence for (int j = 1; j <= m; j++) { if (name[j] == nm)
w[i] = j; } getline(cin, say[i]); say[i].erase(say[i].begin());
// delete say[i] Start space in } for (int td = 1; td <= 7; td++) { // What day is it today for (int px =
1; px <= m; px++) { // What's the serial number of the violent criminal err = 0; // Clear mark memset(judge, 0,
sizeof(judge)); // Initialize to unclear true or false // Judge each sentence in turn for (int i = 1; i <= p; i++) { int who
= w[i]; // The number of the person who said this // If a person is a criminal , And said he was a criminal , Is telling the truth , Otherwise it's a lie if (say[i] == "I am
guilty.") sset(who, px == who ? 1 : -1); // If a person is not a criminal , And say you're not a criminal , Is telling the truth , Otherwise it's a lie
if (say[i] == "I am not guilty.") sset(who, px != who ? 1 : -1);
// If a person says what day is today , Right is the truth , A mistake is a lie for (int j = 1; j <= 7; j++) { if (say[i] ==
day[j]) sset(who, j == td ? 1 : -1); } // If one person says others are not criminals , Right is the truth , A mistake is a lie for (int
j = 1; j <= m; j++) { if (say[i] == name[j] + " is guilty.") sset(who, j == px
? 1 : -1); if (say[i] == name[j] + " is not guilty.") sset(who, j != px ? 1 :
-1); } } int cnt = 0; // Number of liars int no = 0; // The number of people who don't know whether it's true or not for (int i = 1; i <= m;
i++) { if (judge[i] == -1) // false cnt++; if (judge[i] == 0) // unclear no++; }
// If appear Impossible Situation ,err = 1, There are contradictions // If cnt<=n<=cnt+no, That is, the assumption is reasonable if (!err && cnt <= n
&& cnt + no >= n) { if (nx && nx != px) { // If there are two reasonable criminals cout << "Cannot
Determine"; return 0; } else { nx = px; } } } } if (!nx) cout << "Impossible";
else cout << name[nx]; return 0; }
Technology