《算法竞赛宝典》基础算法艺术(公开课程)

【问题描述】推理游戏（BlackVienna.cpp/c/pas）POJ 3915

让李旭琳大跌眼镜的是，小墨老师对学习魔法知识并不是很上心，他天天沉迷于各种游戏之中，例如，他现在又和同学们玩起了Black Vienna游戏，该游戏的规则是这样的：有18张牌，分别标着A~R，游戏有三个人。游戏开始的时候每个人拿5张牌，剩下三张牌隐藏起来，大家都只能看见自己手中的牌。之后，从第一个人到第三个人轮流拿一张“审问牌”去问另外的一个人，“审问牌”上有三个字母，那个人必须诚实地回答自己手中有多少“审问牌”中的字母。哪个人能够最先推断出隐藏起来的牌是什么，那个人就取得胜利。现在你的任务是，给出三个人手上的牌和询问情况，你需要计算出最早在哪一次询问之后，有人能够推断出隐藏的牌。　

例如三个玩家的初始状态为：

玩家1: DGJLP; 玩家2: EFOQR; 玩家3: ACHMN; 隐藏牌: BIK

第1回合:玩家１审问玩家２有无BJK; 回答为0

第2回合:玩家2审问玩家３有无ABK; 回答为1

第３回合:玩家３审问玩家２有无 DEF;回答为2

第4回合:玩家 1审问玩家2有无 EIL; 回答为1

第5回合:玩家2审问玩家3有无 FIP; 回答为0

第6回合:玩家3审问玩家１有无GMO; 回答为1

第7回合:玩家 1审问玩家２有无OQR;回答为 3

第8回合:玩家 2 审问玩家３有无ADQ; 回答为1

第9回合:玩家 3审问玩家1有无EGJ;回答为2

事实上，玩家１能在第８回合判断出隐藏牌是BIK。

【输入格式】

输入最多有12组测试数据，所有测试数据结束以０表示。每组测试数据第一行为一整数t，表示审问次数。且2 ≤ t ≤ 15。

下一行包含四个以空格分隔的字符串，表示三个玩家的牌和隐藏牌。

接下来的t行数据为每回合的数据，即审问者和被审问者，审问字母的字符串及被审问者提供的答案。

所有的字符串为从A到R的唯一字母，按严格递增的顺序排列。同样的查询字符串可能出现在多个回合的游戏。

【输出格式】

输出最早第几回合，即有玩家判断出隐藏牌。若无玩家能判断出，则输出字符串“?”。

【输入样例】

9

DGJLP EFOQR ACHMN BIK

2 BJK 0

3 ABK 1

2 DEF 2

2 EIL 1

3 FIP 0

1 GMO 1

2 OQR 3

3 ADQ 1

1 EGJ 2

3

ABCDE FGHIJ KLMNO PQR

3 BKQ 1

1 ADE 3

2 CHJ 2

0

【输出样例】

8

?