UVA 592 - Island of Logic

The Island of Logic has three kinds of inhabitants: divine beings that always tell the truth, evil beings that always lie, and human beings that are truthful during the day and lie at night. Every inhabitant recognizes the type of every other inhabitant.

A social scientist wants to visit the island. Because he is not able to distinguish the three kinds of beings only from their looks, he asks you to provide a communication analyzer that deduces facts from conversations among inhabitants. The interesting facts are whether it is day or night and what kind of beings the speakers are.

 

Input 

The input file contains several descriptions of conversations. Each description starts with an integer n, the number of statements in the conversation. The following n lines each contain one statement by an inhabitant. Every statement line begins with the speaker's name, one of the capital letters A, B, C, D, E, followed by a colon `:'. Next is one of the following kinds of statements:

 

• I am [not] ( divine | human | evil | lying ).
• X is [not] ( divine | human | evil | lying ).
• It is ( day | night ).

Square brackets [] mean that the word in the brackets may or may not appear, round brackets () mean that exactly one of the alternatives separated by | must appear. X stands for some name from A, B, C, D, E. There will be no two consecutive spaces in any statement line, and at most 50 statements in a conversation.

The input is terminated by a test case starting with n = 0.

 

Output 

For each conversation, first output the number of the conversation in the format shown in the sample output. Then print ``This is impossible.'', if the conversation cannot happen according to the rules or ``No facts are deducible.'', if no facts can be deduced. Otherwise print all the facts that can be deduced. Deduced facts should be printed using the following formats:

 

• X is ( divine | human | evil ).
• It is ( day | night ).

X is to be replaced by a capital letter speaker name. Facts about inhabitants must be given first (in alphabetical order), then it may be stated whether it is day or night.

The output for each conversation must be followed by a single blank line.

 

Sample Input 

1
A: I am divine.
1
A: I am lying.
1
A: I am evil.
3
A: B is human.
B: A is evil.
A: B is evil.
0

 

Sample Output 

Conversation #1
No facts are deducible.

Conversation #2
This is impossible.

Conversation #3
A is human.
It is night.

Conversation #4
A is evil.
B is divine.

 

比较繁琐，思维要缜密。

参考了 http://jianquan.iteye.com/blog/1663651

heavy comment

 

#define RUN
#ifdef RUN

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <list>
#include <cctype> 
#include <algorithm>
#include <utility>
#include <math.h>
#include <ctime>

using namespace std;

#define MAXN 60

typedef struct Statement{
	// Speaker: [A|B|C|D|E]
	// Subject: [A|B|C|D|E|t]	t:It
	// Status: [d|h|e|l|d|n] d:divine, h:human, e:evil, l:lying, d:day, n:night
	char speaker, subject, status;
	bool positive;
}Statement;

Statement stmt[MAXN];
int lines;
int res[5][4];//保存枚举的结果

void printout(){
	for(int i=0; i<lines; i++){
		cout << "lines:" << i << ",speaker:" << stmt[i].speaker << ",subject:" << stmt[i].subject << ",status:" << stmt[i].status << ",positive:" << stmt[i].positive << endl;
	}
}

void printout2(){
	for(int i=0; i<5; i++){
		for(int j=1; j<=3; j++){
			cout << res[i][j] << " ";
		}
		cout << endl;
	}
}

void saveString(string s){

	//构建一个没有空格的s
	string s2 = "";
	for(int i=0; i<s.length(); i++){
		if(s[i] != ' '){
			s2 += s[i];
		}
	}

	//cout << s2 << endl;

	stmt[lines].speaker = s2[0];


	//输入的是关于day或者night的
	//eg，A:Itisday. 或 A:Itisnight.
	if(s2[3] == 't'){
		stmt[lines].subject = s2[3];
		stmt[lines].status = s2[6];
		stmt[lines].positive = true;
	}
	else{
		
		if(s2[2] == 'I'){
			stmt[lines].subject = stmt[lines].speaker;
		}
		else{
			stmt[lines].subject = s2[2];
		}

		//包含了not
		if(s2[5] == 'n'){
			stmt[lines].status = s2[8];
			stmt[lines].positive = false;
		}
		else{
			stmt[lines].status = s2[5];
			stmt[lines].positive = true;
		}
	}

	lines++;
}

bool judge(int X, int T, bool positive, char status){
	//For X:  1:divine, 2:evil, 3:human
	//For T:  1:day, 2:night
	//For positive: true | false
	//For status:  [d|h|e|l] d:divine, h:human, e:evil, l:lying
	
	char XX;
	switch(X){
	case 1:
		XX = 'd';	break;
	case 2:
		XX = 'e';	break;
	case 3:
		XX = 'h';	break;
	}

	//先判断关于lying的问题
	// is lying
	if(status=='l' && positive){
		//如果对方真的在撒谎，则要么对方是evil，要么对方是晚上的human
		if(XX=='e' || (XX=='h' && T==2)){
			return true;
		}
		else{
			return false;
		}
	}
	
	
	if(status=='l' && !positive){	// is NOT lying
		// 如果对方真的没有在撒谎，则要么对方是divine，要么对方是白天的human
		if(XX=='d' || (XX=='h' && T==1)){
			return true;
		}
		else{
			return false;
		}
	}

	//在判断关于角色的问题
	//同真同假
 	if((status==XX) == positive){
		return true;
	}
	else{
		return false;
	}
}


bool isLegal(int A, int B, int C, int D, int E, int T, int i){
	// Speaker: [A|B|C|D|E]
	// Subject: [A|B|C|D|E|t]	t:It
	// Status: [d|h|e|l|d|n] d:divine, h:human, e:evil, l:lying, d:day, n:night
	char speaker = stmt[i].speaker;
	char subject = stmt[i].subject;
	char status = stmt[i].status;
	bool positive = stmt[i].positive;

	//根据假设条件和所说的话来判断该话是否为真
	bool stateIsTrue = false;
	
	//根据subject来区别判断
	//先判断时间
	if(subject == 't'){
		char time;
		if(T == 1){
			time = 'd';
		}
		else{
			time = 'n';
		}

		//判断假设与说的话是否相同
		stateIsTrue = (time==status);
	}
	else{
		// Subject: [A|B|C|D|E]
		// Status: [d|h|e|l] d:divine, h:human, e:evil, l:lying
		// 再根据subject区别判断
		switch (subject)
		{
		case 'A':
			stateIsTrue = judge(A, T, positive, status);
			break;
		case 'B':
			stateIsTrue = judge(B, T, positive, status);
			break;
		case 'C':
			stateIsTrue = judge(C, T, positive, status);
			break;
		case 'D':
			stateIsTrue = judge(D, T, positive, status);
			break;
		case 'E':
			stateIsTrue = judge(E, T, positive, status);
			break;
		}
	}


	//对照stateIsTrue判断假设是否符合说话人speaker的身份
	if(stateIsTrue){
		//divine或者白天的human说的话必需为真
		switch (speaker)
		{
		case 'A':
			if(A==1 || (A==3 && T==1)){
				return true;
			}
			else{
				return false;
			}
		case 'B':
			if(B==1 || (B==3 && T==1)){
				return true;
			}
			else{
				return false;
			}
		case 'C':
			if(C==1 || (C==3 && T==1)){
				return true;
			}
			else{
				return false;
			}
		case 'D':
			if(D==1 || (D==3 && T==1)){
				return true;
			}
			else{
				return false;
			}
		case 'E':
			if(E==1 || (E==3 && T==1)){
				return true;
			}
			else{
				return false;
			}
		}
	}
	else{
		//evil或者晚上的human说的话必需为假
		switch (speaker)
		{
		case 'A':
			if(A==2 || (A==3 && T==2)){
				return true;
			}
			else{
				return false;
			}
		case 'B':
			if(B==2 || (B==3 && T==2)){
				return true;
			}
			else{
				return false;
			}
		case 'C':
			if(C==2 || (C==3 && T==2)){
				return true;
			}
			else{
				return false;
			}
		case 'D':
			if(D==2 || (D==3 && T==2)){
				return true;
			}
			else{
				return false;
			}
		case 'E':
			if(E==2 || (E==3 && T==2)){
				return true;
			}
			else{
				return false;
			}
		}
	}
}



void test(){

	int A, B, C, D, E, T;
	int i;

	int day=0,night=0;
	memset(res,0,sizeof(res)); 

	//1:divine, 2:evil, 3:human
	for(A=1; A<=3; A++){
		for(B=1; B<=3; B++){
			for(C=1; C<=3; C++){
				for(D=1; D<=3; D++){
					for(E=1; E<=3; E++){

						//时间参数，1为白天，2为晚上
						for(T=1; T<=2; T++){

							//检测lines行说的话
							for(i=0; i<lines; i++){
								if(!isLegal(A,B,C,D,E,T,i)){
								//if(!islegal(i,A,B,C,D,E,T)){
									break;
								}
							}

							//表示检验通过
							if(i == lines){
								//cout << "A:" << A << ",B:" << B << ",C:" << C << ",D:" << D << ",E:" << E << endl;
								res[0][A]=1;  
								res[1][B]=1;  
								res[2][C]=1;  
								res[3][D]=1;  
								res[4][E]=1;

								if(T == 1){
									day = 1;
								}
								else{
									night = 1;
								}
							}
						}
					}
				}
			}
		}
	}

	//printout2();


	int impossible=0,nodeducible=1;

	//关于角色的判定
	for(int i=0;i<5;i++)  
	{
		int cnt=0,index;  
		for(int j=1;j<=3;j++){
			if(res[i][j])  
			{  
				cnt++;  
				index=j;  
			}
		}

		//说明X的条件不符合3种角色中的任意一种
		if(cnt==0)  
		{
			impossible=1;  
			break;  
		}
		else if(cnt==1)		//合理的情况是，X只担任一种角色
		{
			char person = i + 'A';
			if(index==1)  
				cout<<person<<" is divine."<<endl;  
			else if(index==2)  
				cout<<person<<" is evil."<<endl;  
			else  
				cout<<person<<" is human."<<endl;  
			nodeducible=0;
		}
	}

	//关于时间的判定
	if(!day && !night) impossible=1;  
	else if(day && !night)   
	{  
		cout<<"It is day."<<endl;  
		nodeducible=0;  
	}  
	else if(night && !day)  
	{  
		cout<<"It is night."<<endl;  
		nodeducible=0;  
	}

	if(impossible) cout<<"This is impossible."<<endl;  
	else if(nodeducible) cout<<"No facts are deducible."<<endl;  
	putchar('\n');  
}


int main(){

#ifndef ONLINE_JUDGE
	freopen("592.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif

	int n;
	int cases=0;

	cin >> n;
	//cout << "n:" << n << endl;
	getchar();
	while(n != 0){
		cases++;
		cout << "Conversation #" << cases << endl;  
		while(n--){
			string s;
			getline(cin, s);

			//cout << "n:" << n << endl;
			//cout << "s:" << s << endl;

			saveString(s);
		}

		//printout();
		test();


		cin >> n;
		getchar();
		memset(stmt, 0, sizeof(stmt));
		lines = 0;
	}


}


#endif