竞赛基础算法

【题目描述】推理游戏（BlackVienna）POJ 3915

小光和同学们玩起了Black Vienna游戏，该游戏的规则是这样的：有18张牌，分别标着A~R，游戏有三个人。游戏开始的时候每个人拿5张牌，剩下三张牌隐藏起来，大家都只能看见自己手中的牌。之后，从第一个人到第三个人轮流拿一张“审问牌”去问另外的一个人，“审问牌”上有三个字母，那个人必须诚实地回答自己手中有多少“审问牌”中的字母。哪个人能够最先推断出隐藏起来的牌是什么，那个人就取得胜利。现在你的任务是，给出三个人手上的牌和询问情况，你需要计算出最早在哪一次询问之后，有人能够推断出隐藏的牌。　

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

玩家1：DGJLP；玩家2：EFOQR；玩家3：ACHMN；隐藏牌：BIK

第1回合：玩家1审问玩家2有无BJK; 回答为0

第2回合：玩家2审问玩家3有无ABK; 回答为1

第３回合：玩家3审问玩家2有无 DEF;回答为2

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

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

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

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

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

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

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

【输入格式】

输入最多有12组测试数据，所有测试数据结束以0表示。每组测试数据第一行为一整数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

?