#THU20162C. 麻将猜猜猜
麻将猜猜猜
时间限制: 1.0 秒
空间限制: 512 MB
题目描述
晨晨和小璐最近在一副麻将牌的基础上,设计出了一款不知怎么取名字的游戏,游戏具体规则如下:
游戏使用以下 张麻将牌或其中一部分牌进行,这 张牌分为万牌、条牌、饼牌三种牌型,每种牌型 张,分别为一万()、二万()……九万(),一条()、二条()……九条(),一饼()、二饼()……九饼(),每张牌有且仅有一张。这副麻将牌比较特殊,每张牌背面都标有这张牌的牌型。
两名游戏玩家,相对而坐,游戏开始时,每个人分配等量的若干张牌,剩余的牌叠好,构成一个牌库。玩家将牌自左向右排成一排。任何时刻都保证:玩家面前任意两张相邻的牌,较小的那张牌在左侧。任意两张牌的大小定义为:若数字不相同,则数字较小的牌较小;若数字相同,万牌()比条牌()小,万牌()、条牌()都比饼牌()小。任何时刻,每个人知道自己所有牌的信息,还知道对方每一张牌的牌型,即知道对方的每一张牌是万牌/条牌/饼牌。
游戏开始之后,双方轮流进行自己的回合。每回合中,当前进行回合的玩家先从牌库最上面摸一张牌并观看,之后按照自己的猜牌策略(详见后述),指定对方的一张牌,并猜其数字是多少。如果猜对了,对方那张被猜中的牌就会被亮出,之后当前进行回合的玩家将自己摸进的这张牌按照大小插入自己的牌序列中适当的位置;猜错了,作为惩罚,需将自己刚摸进的这张牌亮出,之后将自己摸进的这张牌按照大小插入自己的牌序列中适当的位置。
特殊地,如果牌堆里的牌已经摸完,而游戏尚未结束,则回合中不再进行摸牌,只进行猜牌,若猜对,对方被猜中的牌就会被亮出,若猜错则什么也不会发生。另外,游戏中玩家不能猜对方的某张牌是目前已经被自己摸到的某张牌。
对于一方被亮出的牌,另一方能知道这张牌是什么数字(这张牌的牌型在亮出前另一方已经知道)。同时,玩家能够看到对方的牌序列发生的变化,即知道新摸进的牌插入的位置。双方玩家各自知道的信息有:自己的牌、自己对对方的哪张牌猜过哪些数字、对方每张牌的牌型、对方已经亮出的牌的数字,对方不会猜已经摸到的牌,但不知道对方的猜牌策略。
某一时刻,如果某玩家所有牌已经全数亮出,则该玩家输,游戏结束。
晨晨的猜牌策略是:每次都猜小璐的牌序列中最小的未亮出的牌,猜的数字是根据自己掌握的信息,计算出的可能的最大数;小璐的猜牌策略是:每次都猜晨晨的牌序列中最大的未亮出的牌,猜的数字是根据自己掌握的信息,计算出的可能的最小数。
现在给出游戏开始时双方分配到的牌,牌库从顶至底的牌的顺序,请回答:若晨晨先进行回合,谁是胜利者,游戏结束时,获胜者还有多少张牌没有亮出来。
输入格式
从标准输入读入数据。
共三行字符串,第一行用一个字符串描述游戏开始时,晨晨手里的若干张牌;第二行用一个字符串描述游戏开始时,小璐手里的若干张牌;第三行依次描述的是牌堆自顶而下每张牌,保证无多余空格与回车。
描述格式如下:每个字符串都由 个字符组成,每两个字符表示一张牌,第一个字符为牌的数字,第二个字符为牌的牌型,例如 、、,分别表示一万、六条、九饼。
输出格式
输出到标准输出。
第一行一个字符,表示获胜者, 表示晨晨, 表示小璐;
第二行一个数字,表示游戏结束时,获胜者还有多少张牌没有亮出来(如果这个回合获胜者有进行摸牌,则包括刚摸进的那张牌)。
1W
9W
2W3W4W5W6W7W8W
C
2
样例 1 解释
样例1的解释:晨晨的第一个回合摸进一张牌二万(),她知道对方只有一张万牌,对方最小的为亮出的牌是九万(),晨晨会猜可能的最大数九万(),猜测正确,小璐所有的牌都已经亮出,所以晨晨获胜,算上刚摸进的二万(),晨晨胜利时还有一万()、二万()共两张牌未亮出。
1W1T1B
3W4W5W
2W2T3T4T5T6T7T8T2B3B4B5B6B7B8B6W7W8W9W9T9B
L
6
提示
- 游戏开始时双方的若干张牌可能尚未排序。
- 双方游戏开始时分配到的牌+牌堆里的牌可能仅包含部分牌型,但一定包含该牌型的所有牌,例如,此局游戏只含有万牌,则牌堆为一万到九万,共 张牌。
- 根据两人的策略和知道的信息,我们可以推出晨晨的具体计算方法为:先考虑对方序列中没有亮出的最大的牌,推测它最大可能是哪一张牌,接着基于之前的推测继续考虑次大的未亮出的牌,直到序列最小的那张未亮出的牌;小璐的具体计算方法为:先考虑对方序列中没有亮出的最小的牌,推测它最小可能是哪一张牌,接着基于之前的推测继续考虑次小的未亮出的牌,直到序列最大的那张未亮出的牌。
子任务
| 测试点 | 总牌堆牌型数 | 玩家起始牌数 | 特殊说明 |
|---|---|---|---|
| 数据保证在双方进行各自的第二个回合前结束游戏 | |||
| 无 | |||
| 数据保证在双方进行各自的第二个回合前结束游戏 | |||
| 无 | |||
| 数据保证晨晨摸到的牌总是比她当前序列里的最小牌小,小璐摸到的牌总是比她当前序列里的最大牌大(注意:玩家不知道这一性质) | |||
| 双方玩家起始 张万牌 张条牌 | |||
| 数据保证在双方进行各自的第二个回合前结束游戏 | |||
| 无 | |||
| 数据保证晨晨摸到的牌总是比她当前序列里的最小牌小,小璐摸到的牌总是比她当前序列里的最大牌大(注意:玩家不知道这一性质) | |||
| 双方玩家起始 张万牌 张条牌 张饼牌 | |||
| 无 | |||
牌型数指本局游戏使用的牌中,有多少种不同的牌型(万牌、饼牌、条牌)。
起始牌数指游戏开始时,每名玩家分配到的牌的数量。