Acwing478 detective reasoning

Title Description

Question link: 478. Detective reasoning - AcWing question bank

Mingming recently fell in love with the detective cartoon Conan and indulged in the reasoning game, so he called a group of students to play the reasoning game.

The content of the game is like this. Mingming's classmates first discuss that one of them should act as a criminal (without knowing it). Mingming's task is to find out the criminal.

Then, clearly ask each student one by one. The inquired person may say:

Content of testimony	Meaning of testimony
I am guilty.	I'm a criminal
I am not guilty.	I'm not a criminal
XXX is guilty.	XXX is a criminal (XXX means the name of a classmate)
XXX is not guilty.	XXX is not a criminal
Today is XXX.	Today is XXX (XXX means the day of the week, which is one of Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday)

Other words appearing in the testimony are not included in the content of logical reasoning.

What Mingming knows is that one of his classmates always tells lies, and the rest always tells the truth.

Now, Mingming needs your help to infer who is the real murderer from his classmates' words. Please remember, there is only one murderer!

Input format

The input consists of several lines. The first line has three integers, M, NM, N and PP; MM is the number of students who participated in the game, NN is the number who always lied, and PP is the total number of testimony.

Next, MM lines, each line is the name of a classmate (composed of English letters, no spaces, all capitalized).

Then there are PP lines. Each line starts with the name of a classmate, followed by a colon and a space, followed by a sentence of testimony, which conforms to the format listed in the previous table.

Each line of testimony shall not exceed 250250 characters.

There are no two consecutive spaces in the input, and there are no spaces at the beginning and end of each line.

Output format

If your program can determine who is the criminal, output his name; If the program judges that more than one person may be a criminal, it outputs Cannot Determine; If the program judges that no one is likely to become a criminal, it outputs Impossible.

Data range

1≤M≤201≤M≤20,
1≤N≤M1≤N≤M,
1≤P≤1001≤P≤100

Input sample:

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 example:

MIKE

Algorithm idea

At first, I thought about enumerating n people who lied, but in this case, there will be \ (2^{n} \), and the time complexity is a little too large. After thinking about it, just enumerate the M people who are the murderers, and then cycle every day of the week. Because there is only one murderer, each testimony can judge whether it is correct or wrong. Ideally, the number of liars can be directly calculated, so as to directly judge whether it is equal to n. However, in the actual situation, some people may not speak, or even some people tell the truth and lie, so these special circumstances should be taken into account. If they tell the truth and lie, they can skip this judgment and make the next judgment directly; If some people don't speak or talk nonsense and can't judge whether what they say is true or false, then we can finally judge the number of liars, the number of people who tell the truth and the number of people who can't judge; In this case, if the number of liars is less than or equal to N and the number of liars plus the number of people who cannot judge is greater than or equal to N, then this situation should also be counted. If it is finally found that more than one person may be a criminal, output Cannot Determine; If no one has become a criminal at the end of the program, output Impossible. Theoretically, the time complexity in this case is O(M * 7 * P), but the speaker of each testimony cannot be obtained directly. It is necessary to traverse the array of names. In this case, it is \ (O(7M^{2}P) \). Here is a test of the design of code structure. Modular design method should be used. But I want to be lazy and lazy to write functions from the beginning. Finally, the structure of the code is very cumbersome. I suggest you use modular design when writing complex code. The following yxc solution is very good: AcWing 478. Detective reasoning - acwing.

In addition, this problem also needs to be able to skillfully use the processing method of string. Moreover, this topic has a large amount of input data. For the java language, a faster method to obtain input should be used. I use BufferedReader here.

Introduction to string processing

In this topic, we need to deal with strings. Here we will briefly introduce several common string processing methods. If you are familiar with this part, you can skip this link and look at the following code directly.

1. Basic operation function

int length = str.length();	//Get string length
char c = str.charAt(i);		//Gets the character at index i
char[] characters = new char[N];
str.getChars(begin,end,characters,copybegin);//begin and end are the beginning of the copied string; The array name of the array to which characters are copied; copybegin refers to where characters are pasted.

2. String comparison

When we look up the dictionary, the Pinyin chen is before cheng, and the two pronunciations are also before chun.

The comparison of strings is similar to the dictionary order above, except that the comparison between each character is carried out according to the character set. We usually use ASCII and Unicode in the character set. There are many ASCII in general problems.

int result = str1.compareTo(str2);	//In this case, case is not ignored. For example, uppercase A is smaller than lowercase a. In this case, if the dictionary order of str1 is less than str2, return - 1; Equal to return 0; Greater than 1 returned;
int result = str1.compareToIgnoreCase(str2);//In this case, case is ignored. For example, uppercase A is equal to lowercase a. In this case, if the dictionary order of str1 is less than str2, return - 1; Equal to return 0; Greater than 1 returned;
boolean result = str1.equals(str2);//In this case, case is not ignored. For example, uppercase A is smaller than lowercase a. In this case, if the dictionary order of str1 is equal to str, return 1; Otherwise, it returns 0;
boolean result = str1.equals(str2);//In this case, case is ignored. For example, uppercase A is equal to lowercase a. In this case, if the dictionary order of str1 is equal to str, return 1; Otherwise, it returns 0;

3. String output

We can convert an array into a string and then output it in the form of string. The array can be byte or char.

byte[] b={1,2,333};	//char type can also be used
String str=new String(b);
//String str=new String(b,start,length); // This is the output of the element of length from start
System.out.println(str);

4. Type conversion

String strb1 = String.valueOf(variable); //The variables here can be int/double/float/char/byte/boolean/long and so on

5. String search

The first is to find the occurrence position of specific characters

//The character here can be a character type or a string type. If it is a string, it returns the index number of the first element of the string
int index = str.indexOf(character);	//Find the index of the position where the character first appears in the str string. If it is not found, return - 1;
index = str.indexOf(character,fromIndex); //Find the index of the first occurrence position of character after formIndex in str string. If it is not found, return - 1;
index = str.lastIndexOf(character);		//Find the index of the last occurrence position of the specified character in the string, and - 1 is not returned
index = str.lastIndexOf(character,fromIndex);	//Finds the index number of the last occurrence of the character before the specified index position

6. String interception

String result = str.substring(begin,end)；//Intercept the substring from begin to end; However, note that the actual string obtained here is [begin, end]. For example, substring(3,4) can only intercept one character, and its index number is 3.
String strs[] = str.split(regular expression );		//Splits the string according to the contents of the regular expression
String strs1[] = str.split(" ");		//For example, "Hello World Hei hei" will be divided into four strings, hello,world,hei,hei;
String strs2[] = str.split(" {2，}");	//The delimiter of this is the regular expression "{2,}", which means two or more spaces. "Hello World Hei hei" will be divided into two strings: hello and world Hei hei.

7. Replacement and modification

String result = str1.concat(str2);   //Merge str1 and str2 and save them to result
String result2 = str.toLowerCase();		//Convert all letters in str to lowercase and save them to result2
String result3 = str.toUpperCase();      //Convert all letters in str to uppercase and save them to result2
String result4 = str.replaceFirst(regular expression ,Replace string)；//Search in the string according to the regular expression, and modify the first element found to replace the string.
String result4 = str.replaceAll(regular expression ,Replace string)；//Search in the string according to the regular expression, and modify all the elements found to replace the string.

Implementation code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
public class Main {
	static int M,N,P;	//players,liers,testimonies
	static String names[];	//players names
	static String testimoneies[];
	static String speakers[];
	static String sentences[];
	static Map<String, Integer> map;	//true:lier false:honest
	static BufferedReader in;
	static String days[] = new String[] {"Today is Monday.","Today is Tuesday.","Today is Wednesday.","Today is Thursday.","Today is Friday.","Today is Saturday.","Today is Sunday."};
	public static void main(String args[]) throws IOException{
		in = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);
		M=sc.nextInt();
		N=sc.nextInt();
		P=sc.nextInt();
//		System.out.println(M+N+P);
		names = new String[M];
		testimoneies = new String[P];
		speakers = new String[P];
		sentences = new String[P];
		map = new HashMap<>();
		String name;
		String tempString="";
		//Name array
		tempString=sc.nextLine();
		for(int i =0;i<M;i++) {
			name=sc.nextLine();
//			System.out.println(name);
			names[i]=name;
			map.put(name, -1);
		}
//		System.out.println("start test");
		//Testimony processing
		for(int i =0;i<P;i++) {
			testimoneies[i]=sc.nextLine();
//			System.out.println(testimoneies[i]);
			speakers[i]=testimoneies[i].split(": ",2)[0];
//			System.out.println(speakers[i]);
			sentences[i]=testimoneies[i].split(": ",2)[1];
//			System.out.println(sentences[i]);
		}
		int count=0,num=0,count1=0;
		int state=-1;
		boolean flag=true;
		String speaker,name1,criminal,sentence;	//Store the spokesperson, date and criminal name extracted from the testimony; And the names of the enumerated criminals
		//Cycle assumes that this M person is a criminal
		for(Map.Entry<String, Integer> entry : map.entrySet()) {
			//Get the name of the hypothetical criminal
			criminal=entry.getKey();
//			System.out.println(criminal);
			//The cycle assumes seven days a week. Which day is today
			for(int j=0;j<7;j++) {
				count=0;
				count1=0;
				flag=true;
				//1. Copy the map obtained from the input
				Map<String, Integer> copyMap = new HashMap<>();	
				copyMap.putAll(map);
//				System.out.println(copyMap);
				//2. Circular judgment P sentence testimony
				day:
				for(int k=0;k<P;k++) {
//					System.out.println(testimoneies[k]);
					//1. Get who's talking
					speaker = speakers[k];
					sentence = sentences[k];
//					System.out.println(sentence);
					//2. What you said is about the date
					for(int m =0;m<7;m++) {
						if(sentence.equals(days[m])) {
							state=(m!=j)?1:0;
						if(state+copyMap.get(speaker) != 1)
							copyMap.put(speaker, state);
						else {flag=false;break day;}
						}
					}
					//3. What you said about xxx is / is not a criminal
					if(sentence.toLowerCase().equals("i am guilty.") ) {
						state=(!speaker.equals(criminal))?1:0;
						if(state+copyMap.get(speaker) != 1)
						copyMap.put(speaker, state);
						else {flag=false;;break;}
						}
					else if (sentence.toLowerCase().equals("i am not guilty.")	) {
						state=(speaker.equals(criminal))?1:0;
						if(state+copyMap.get(speaker) != 1)
						copyMap.put(speaker, state);
						else {flag=false;;break;}
					}
					else if(sentence.contains(" is ")&&sentence.split(" is ",2)[1].equals( "guilty.")) {
						name1=sentence.split(" is ",2)[0];
						if(copyMap.get(name1) !=null)
							{
							state=(!name1.equals( criminal))?1:0;
							if(state + copyMap.get(speaker) !=1)
								copyMap.put(speaker, state);
							else {flag=false;;break;}
							}
						else break;
					}
					else if(sentence.contains(" is ")&&sentence.split(" is ",2)[1].equals( "not guilty.")) {
						name1=sentence.split(" is ",2)[0];
						if(copyMap.get(name1) !=null)
							state=(name1.equals( criminal))?1:0;
							if(state + copyMap.get(speaker) !=1)
								copyMap.put(speaker, state);
							else {flag=false;;break;}
					}
					//4. It's nonsense
				}
				if(flag) {
				Iterator<Map.Entry<String, Integer>> it =copyMap.entrySet().iterator();	//Traversal name
				while(it.hasNext()) {
					Map.Entry<String, Integer> en =it.next();
					if(en.getValue() == 1) count++;
					else if(en.getValue() == -1) count1++;
				}
//				System.out.println(copyMap);
				if(count<=N&&count+count1>=N&&(tempString == ""||!tempString.equals(criminal))) {num++;tempString=criminal;}
				if(num>1) break;
				}
			}
		}
		if(num == 0) System.out.println("Impossible");
		else if (num == 1) System.out.println(tempString);
		else System.out.println("Cannot Determine");
	}
}