#P1478. Island of Logic
Island of Logic
题目描述
逻辑岛上居住着三种生物:
- 神族(Divine):永远说真话
- 恶魔(Evil):永远说谎
- 人类(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结束。
输出格式
对于每组对话:
- 首先输出对话编号(如样例所示)
- 如果对话内容自相矛盾,输出"This is impossible."
- 如果无法推断任何事实,输出"No facts are deducible."
- 否则按以下格式输出所有可推断的事实:
- 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年西南欧地区竞赛