网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[POJ2931][MIT2005]拖延游戏
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | procrastination.in | 输出文件 | procrastination.out |
【题目描述】
在很久很久以前,有两名研究生是好朋友。在搞研究的短暂空闲(通常不超过几小时)中,他们喜欢玩拖延游戏。
拖延游戏有两名玩家(分成黑和白),玩家轮流移动。游戏是从塔上移除立方体。每个立方体都是黑色或白色的。最初有4座塔,每座塔都是由立方体组成的一个栈。当轮到某名玩家时,他可以移除他的颜色相同的任意立方体(白色玩家只能移除白色立方体,黑色玩家只能移除黑色立方体)。并且该立方体上方的立方体也会被移除,无论它们的颜色是什么。例如,假设由如下立方体(从下到上)组成的一座塔:黑,白,黑,白。那么,如果黑色玩家移除了最底部的黑色立方体,他就移除了整座塔。黑色玩家也可以移除第三个立方体,则同时就移除了第四个立方体。如果白色玩家移除了第二个立方体,整座塔就只剩下一个黑色立方体了。白色玩家也可以移除第四个立方体。如果一名玩家无法移除任何立方体,他就输了。
由于在大学期间学习了这个游戏的复杂之处,两名研究生知道如何完美地玩这个游戏,也就是说,如果一名玩家有必胜策略,那么这名玩家就一定会赢。但有时候,他们发现了一点:对于大多数初始状态,一名玩家总是有必胜策略,无论谁先移动。他们把初始状态称为W-状态,如果无论谁先移动,白色玩家总是有必胜策略。如果黑色玩家总有必胜策略,则称其为B-状态。
除此之外,他们注意到一些局部状态至少和别的(局部)状态一样对某一名玩家有利。一个局部状态C定义为3座塔的集合,注意到局部状态C加上第四座塔T就是一完整的游戏状态,我们把它记作(C,T)。对于上述“至少和别的状态一样有利”我们正式定义如下。一个局部状态C1(由3座塔组成)至少和局部状态C2(同样包含3座塔)一样对白色玩家有利,当且仅当对于任意的第四座塔T,如果(C2,T)是W-状态那么(C1,T)也是W-状态。换句话说,不存在第四座塔T使得(C1,T)不是W-状态而且(C2,T)是W-状态。
给出两个局部状态C1和C2,你将要判断C1是否至少和C2一样对白色玩家有利。
【输入格式】
输入文件的第一行有一个整数,代表数据组数。
每组数据的格式如下:
第一行形如"Test N",其中N是这组数据的编号。
接下来有8行,按如下格式描述了两个局部状态C1和C2:
局部状态的第一行有三个整数n1,n2,n3,代表这个局部状态中三座塔的高度(0<=n1,n2,n3<=50)。
第二行有n1个空格隔开的字母(B或W),描述了第一座塔。
第三行有n2个空格隔开的字母,描述了第二座塔。
第四行有n3个空格隔开的字母,描述了第三座塔。
字母W代表一个白色立方体,字母B代表黑色立方体。每座塔都按照从下到上的顺序描述。
【输出格式】
对每组数据,输出单独的一行,包含数据编号和Yes(如果C1至少和C2一样对白色有利)或No(其他情况)。
【样例输入】
2
Test 1
3 3 1
W B B
W B W
B
3 3 3
B W W
B W W
W B B
Test 2
3 3 2
W B B
W B W
B B
3 3 3
B W W
B W W
W B B
【样例输出】
Test 1: Yes
Test 2: No
【提示】
数据组数<=10
【来源】
MIT Programming Contest 2005