#6471. 「ICPC World Finals 2017」找出线索!Get a Clue!

内存限制:1024 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tangjz

题目描述

起源于 19 世纪 40 年代的英国的游戏 Cluedo 是世界上最流行的图版游戏之一。游戏的目标是找出谋杀 Boddy 先生的凶手,凶手使用的凶器,以及行凶的地点。游戏使用一系列卡片表示六个角色(标号 A, B, ..., F)、六种武器(标号 G, H, ..., L)和九个房间(标号 M, N, ..., U)。在游戏的开始,角色、武器和房间分别会有一张卡片在玩家不知道的情况下被随机移除,它们分别表示凶手、凶器和作案地点。剩下的 18 张卡片会重新排列并分发给玩家,第一张会给玩家 1,接下来会给他右边的玩家 2,依次类推。一些玩家可能比其他玩家多拿一张牌。由于这道题的原因,玩家的数量为四个,这意味着玩家 4 的右边是玩家 1。

游戏剩下的部分便是寻找线索。玩家轮流决策,从玩家 1 开始,然后依次是其右边的玩家。每轮决策需要提出一个 suggestion(即提议,包括指定嫌疑人、凶器和作案地点)并轮询其他玩家是否有证据能反对这个提议。例如,你可以对另一个玩家说:“我认为凶手是角色 A,凶器是 L,作案房间是 T。”如果其他玩家恰好有其中一张卡片,这个玩家必须向你(且只有你)展示这张卡片。如果他有多张这样的卡片,他可以任选一张向你展示。

当你提出提议时,你需要先问你右手边的玩家是否可以反驳你。如果他没有反驳,你可以继续问这个人右手边的玩家,直到有人提出反驳的证据,或是所有人都无法反驳你的提议。

许多时候你可以从其他人的提议过程中获取信息。例如上面的例子,你是拥有卡片 A 和 T 的第三方玩家。如果有人向提议者展示了反驳的证据,那么你可以知道那张卡片一定是武器 L。在游戏过程中,保持对提议与反驳过程的追踪是很重要的游戏策略。

为了赢得游戏,你需要进行 accusation(即指控),做出你对凶手、凶器和作案地点的最终猜测。在你的指控开始后,你可以检查最开始被移除的三张卡片——如果它们与你的指控相符,你就赢得胜利啦!无需多说,你肯定希望在提出指控前有绝对的把握。

所以有了这道题。你是玩家 1。给定你手上的卡片集合,以及一些提议与反驳的记录,你需要确定你离能够做出指控还有多远。

输入格式

第一行包含一个整数 n (1 \leq n \leq 50) ,表示游戏中已经完成的提议数量。

第二行包含你手上五张卡片的信息,它们是 AU 之间的大写字母。

接下来 n 行,每行给出一条提议的信息。每行以三张卡片开始,依次表示提议的角色、武器和房间,接下来给出剩下三个玩家的响应,从提议者右边的玩家开始。如果一个玩家没有证据反驳,则响应信息是一个 -,否则响应信息是一个证据字符。如果证据对你是可见的 (你是提议者或反驳者) ,则证据字符是对应的卡片,否则证据字符是 *。注意只有最后一条响应信息可以是证据字符。

所有字符之间用一个空格隔开。保证输入的提议和响应序列是合法的。

输出格式

输出三个字符表示能识别出的凶手、凶器和作案地点。如果凶手可以被识别,输出相应的卡片字符,否则输出 ?。凶器和作案地点同理。

样例

样例输入 1

1
B I P C F
A G M - - -

样例输出 1

AGM

样例输入 2

2
A B C D H
F G M M
F H M - *

样例输出 2

E??

样例输入 3

3
A C M S D
B G S - G
A H S - - S
C J S *

样例输出 3

???