#P1478. Island of Logic

    ID: 479 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 10 上传者: 标签>模拟其他Southwestern European Regional Contest 1997

Island of Logic

题目描述

逻辑岛上居住着三种生物:

  1. 神族(Divine):永远说真话
  2. 恶魔(Evil):永远说谎
  3. 人类(Human):白天说真话,晚上说谎

每个居民都能识别其他居民的类型。一位社会科学家想要造访该岛,由于无法通过外貌区分这三种生物,他请你开发一个通信分析器,通过居民间的对话推断以下事实:

  • 当前是白天还是晚上?
  • 每个说话者的身份是什么?

输入格式

输入包含多组对话描述。每组描述以整数n(对话中的语句数量)开头,随后n行每行包含一个居民的陈述。每条陈述的格式为:

  • 说话者名称(A-E的大写字母)后接冒号":"
  • 陈述内容可能是以下之一:
    • I am [not] (divine | human | evil | lying).
    • X is [not] (divine | human | evil | lying).
    • It is (day | night).

方括号[]表示其中的单词可能出现也可能不出现,圆括号()表示必须选择其中一个用"|"分隔的选项。X代表A-E中的某个名称。语句中不会有两个连续空格,每组对话最多50条语句。

输入以n=0结束。

输出格式

对于每组对话:

  1. 首先输出对话编号(如样例所示)
  2. 如果对话内容自相矛盾,输出"This is impossible."
  3. 如果无法推断任何事实,输出"No facts are deducible."
  4. 否则按以下格式输出所有可推断的事实:
    • X is (divine | human | evil). (按字母顺序输出居民身份)
    • It is (day | night). (最后输出时间信息)

每组对话输出后需空一行。

样例输入

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

样例输出

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.

提示

以第三个输入为例(A说"I am evil."):

  • A不可能是神族(否则在说真话但内容矛盾)
  • A不可能是恶魔(否则应该说谎但实际说了真话)
  • 因此A必须是人类,且因为他在说谎,所以必须是晚上

第四个输入示例中:

  • A的两个陈述互相矛盾,说明A在说谎
  • 因此B既不是人类也不是恶魔,只能是神族
  • 由于B说真话,A必须是恶魔

来源

1997年西南欧地区竞赛