[POJ2931][MIT2005]拖延游戏

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file procrastination.in Output file 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

【来源】

POJ 2931 Procrastination

MIT Programming Contest 2005