• 博客访问： 1140163
• 博文数量： 196
• 博客积分： 4141
• 博客等级： 中将
• 技术积分： 2253
• 用 户 组： 普通用户
• 注册时间： 2009-03-21 20:04

2019年（31）

2016年（1）

2014年（16）

2011年（8）

2010年（25）

2009年（115）

2009-06-24 16:21:45

Island of Logic

 Time Limit:1s Memory limit:32M Accepted Submit:5 Total Submit:10

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

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

### Sample Output

`Conversation #1No facts are deducible.Conversation #2This is impossible.Conversation #3A is human.It is night.Conversation #4A is evil.B is divine.`

 ```#include #include #include char str_name[][10] = {"", "divine.", "human.", "evil.", "lying.", "day.", "night."}; struct Data {     char author;     char master;     char isornot;     int beings; }; struct Data data[100]; char beings_day[6]; char out_day[6]; int answer[6]; int day; int num; int verity() {     int i;     for (i = 0; i < num; ++i)     {         if ((beings_day[data[i].author] == 1 && data[i].isornot) || (beings_day[data[i].author] == 3 && !data[i].isornot) ||             (beings_day[data[i].author] == 2 && beings_day[5] == 5 && data[i].isornot) ||             (beings_day[data[i].author] == 2 && beings_day[5] == 6 && !data[i].isornot))         {             if (data[i].beings == 4)             {                 if (beings_day[data[i].master] == 3)                     return 0;                 else if (beings_day[data[i].master] == 2)                 {                     if (beings_day[5] == 6)                         return 0;                 }             }             else             {                 if (data[i].beings == beings_day[data[i].master])                     return 0;             }         }         else         {             if (data[i].beings == 4)             {                 if (beings_day[data[i].master] == 1)                     return 0;                 else if (beings_day[data[i].master] == 2)                 {                     if (beings_day[5] == 5)                         return 0;                 }             }             else             {                 if (data[i].beings != beings_day[data[i].master])                     return 0;             }         }     }     for (i = 0; i < 6; ++i)     {         if (out_day[i] == beings_day[i])             continue;         answer[i]++;         out_day[i] = beings_day[i];     }     return 0; } int run(int author) {     int i;     if (author >= 6)     {         verity();         return 0;     }     if (author == 5)     {         if (day != 0)         {             for (i = 5; i <= 6; ++i)             {                 beings_day[author] = i;                 run(author + 1);             }         }         else         {             beings_day[5] = -1;             run(author + 1);         }     }     else if (beings_day[author] == -1)         run(author + 1);     else     {         for (i = 1; i <= 3; ++i)         {             if (i == 2)                 ++day;             beings_day[author] = i;             run(author + 1);             if (i == 2)                 --day;         }     }     return 0; } int main() {     int i, j, count, flag;     char str[10], str1[10];     count = 0;     while (scanf("%d", &num) && (num != 0))     {         day = 0;         memset(beings_day, -1, sizeof(beings_day));         memset(answer, 0, sizeof(answer));         memset(out_day, -1, sizeof(out_day));         for (i = 0; i < num; ++i)         {             scanf("%s %s", str, str1);             data[i].author = str[0] - 'A';             if (strcmp(str1, "I") == 0)                 data[i].master = data[i].author;             else if (strcmp(str1, "It") == 0)             {                 ++day;                 data[i].master = 5;             }             else                 data[i].master = str1[0] - 'A';             scanf("%s %s", str, str1);             if (strcmp(str1, "not") == 0)             {                 data[i].isornot = 1;                 scanf("%s", str1);             }             else                 data[i].isornot = 0;             j = 1;             while (strcmp(str1, str_name[j]) != 0) ++j;             data[i].beings = j;             beings_day[data[i].author] = 0;             beings_day[data[i].master] = 0;         }         run(0);         ++count;         printf("Conversation #%d\n", count);         flag = 0;         for (i = 0; i < 6; ++i)         {             if (answer[i] == 1)             {                 if (i == 5)                     printf("It is %s\n", str_name[out_day[i]]);                 else                     printf("%c is %s\n", i + 'A', str_name[out_day[i]]);                 flag |= 1;             }             else if (answer[i] > 1)                 flag |= 2;         }         if (flag == 0)             printf("This is impossible.\n");         else if (flag == 2)             printf("No facts are deducible.\n");         printf("\n");     }     return 0; }```