SPOJ.com - Problem LOGIC2

LOGIC2 - Logic II

Some day in 2003 in Byteland began calm and quietly as any other day. Some people went to work, some to school, some to store to buy food. Drivers were traditionally stucked in traffic jams, drinking coffee and reading morning newspaper. Suddenly the regularity of this day was disturbed by huge explosion."They blew up the embassy of Bajtocja!!!" somebody cried. Everybody began to run away in panic.

Police works pretty good in Byteland and first radiocars appeared near the embassy only few seconds after the explosion. All the people near the embassy were detained. Only one of the people is the organizer of the explosion, the others could by just occasional witnesses. It is known, among these M(1<=M<=11) people, N(1<=N<=M) people always lie because they want to make the work of police more difficult, the others always tell the truth.

All these people say P(1<=P<=30) sentences in total.All the useful sentences are in one of the 4 forms below, all the other sentences are useless and you can ignore them.

I am guilty.
I am not guilty.
Somebody is guilty.
Somebody is not guilty.
Today is Someday.

Among these sentences, Somebody is a name of one of these M people, and Someday is Monday, Tuesday, Wednesday, Thursday, Friday, Saturday or Sunday.

Your task is to help the police to find out the only one organizer of the explosion.

Input

Multiple test cases. For each test case:

The first line contains three integers M, N and P. M lines follow, each contains a name of one of the people.All names contain only capital Latin letters and no whitespaces.P lines come next, each contains no more than 250 characters, the speaker and his/her speech. See the example.

You can assume that there's no whitespace at the start and the end of a line, and there are no two consecutive spaces in the input.

Input terminate by EOF.

Output

The name of the organizer if you can determine, or Cannot Determine if you find more than one person is possible, or Impossible if you find the situation is contradictory.

Example

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

Submit solution!

Added by:	Fudan University Problem Setters
Date:	2007-07-13
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: C99 ERL JS-RHINO
Resource:	Description by Blue Mary

hide comments



2024-02-09 09:56:10 Sushovan Sen What is expected output for following case 3 1 9 MIKE CHARLES TOM CHARLES: Mike is guilty. TOM: Mike is guilty. MIKE: Today is Sunday MIKE: Today is Monday MIKE: Today is Tuesday MIKE: Today is Wednesday MIKE: Today is Thursday MIKE: Today is Friday MIKE: Today is Saturday is it MIKE or IMPOSSIBLE
2020-06-10 20:33:13 Simes For a question about logic, there's some dubious logic being used in the psetter's answer to @mud's first query - if Charles is the liar, it does not mean there's no organiser, but in the absence of any other statement about guilt, it would mean we can't tell who the organiser is. These are not the same thing at all. Since we can't tell who the organiser is, the answer should surely be Cannot Determine? I realise you're not going to change the expected answer now, but perhaps you can update the statement to clarify. @nadstratosfer, wouldn't this case also result in Impossible? 3 1 3 MIKE CHARLES TOM MIKE: I am guilty. CHARLES: I am guilty. TOM: I am guilty. [NG]: Going through the possibilities, the police only names a suspect if there's exactly one pointed at by the set of statements, otherwise the set is not considered in the investigation. We can determine the organizer if all considered sets name the same suspect. The answer is Impossible only if there's a witness who cannot possibly be assumed to be telling only truth or only lies. [Simes]: @NG thank you, and congratulations on your promotion to moderator. Perhaps the problem statement should be updated to explain that, rather than output "Impossible if you find the situation is contradictory." And the "logic" that identifies Charles is simply flawed. Charles could be the liar, and the statements are then all consistent with an unidentified perp. [NG]: There is no unidentified perp, everyone was detained and gave statements. The cops take the version of events that makes sense. I agree that the criteria for Impossible were blurry before comments though. Last edit: 2020-06-11 22:28:33
2020-05-18 05:33:39 ok thank you @nadstratosfer
2020-05-17 21:05:34 AC due to mud's research and BlueMary's (or Francky's?) response to his comment, thanks. My solution outputs "Impossible" only in case of internal conflict between statements of the same witness. =(Francky)=> I always sign mine... It can be the psetter. ;-) Last edit: 2020-05-18 19:16:30
2020-05-17 09:34:16 i found at http://discuss.spoj.com/t/problem-1687-logic2/1308 Some test case: Input: 3 1 1 MIKE CHARLES KATE MIKE: How are you?? Output: Cannot Determine as long as there are no any statement about who's guilty, they are considered as organizer?
2020-05-14 19:12:13 3 1 5 MIKE CHARLES JOHNY MIKE: Today is Sunday. CHARLES: I am guilty. JOHNY: How are you? CHARLES: OKAY. JOHNY: Never mind. Liar can be CHARLES or MIKE or JOHNY, so the organizer can be 1 or 0, so what is the output? ==(RE)==> If the liar is MIKE or JOHNY, the organizer must be CHARLES; If the liar is CHARLES, the number of organizer is 0 which is contradictory to "The number of organizer is exactly 1" in problem description. So the answer should be "CHARLES". Last edit: 2020-05-17 04:59:27
2015-04-05 13:59:00 :.Mohib.: Confusing.....plzz explain the sample case...