procrastination---불평등 게임

Procrastination
Time Limit: 5000MS
 
Memory Limit: 65536K
Total Submissions: 455
 
Accepted: 98
Description
Once upon a time, there were two graduate students that were best friends. During their short breaks from research (usually, not longer than several hours), the two students liked to play the game of Procrastination.
The game of Procrastination is for two players (black and white), who take turns moving. The game involves removing cubes from towers. Each cube is either black or white. At the start of the game, these cubes are arranged into 4 towers: each tower is a stack of several cubes. On a player’s turn, he can remove any cube that matches his color (the white player removes only white cubes, and the black player only removes black cubes). All the cubes above the chosen cube are also removed from the tower, irrespective of color. For example, suppose a tower is composed of the following cubes (from bottom to top): black, white, black, white. Then, if black removes the bottom-most black cube, he removes the entire tower, black can also take the 3rd cube, removing the 4th cube with it. If white removes the 2nd cube, then only one black cube will remain, white can also take the 4th cube. If a player cannot remove any cubes, he loses.
Having already been trained in the intricacies of the game during their undergraduate years, the two students learned to play the game perfectly, i.e., if a player had a winning strategy, then that player would win the game. However, at some time, they discovered that, for most starting configurations, one of the players has the winning strategy irrespective of which player moves first. They called a configuration a W-configuration if white has a winning strategy irrespective of who moves first, and a B-configuration if black has a winning strategy irrespective of who moves first.
Moreover, the friends noted that some partial configurations are at least as favorable for one player as other configurations. A partial configuration C is defined as a set of 3 towers, note that a partial configuration C together with a 4th tower T forms a complete game configuration, which we denote as (C, T). A formal definition of the notion “at least as favorable”, is as follows. A partial configuration C1 (composed of 3 towers) is at least as favorable for white as another partial configuration C2 (also composed of 3 towers) if and only if for any 4th tower T, if (C2, T) is a W-configuration then (C1, T) is also a W-configuration. In other words, there does not exist a 4th tower T such that (C1, T) is not a W-configuration and (C2, T) is a W-configuration.
Given two partial configurations C1 and C2, you are to check whether C1 is at least as favorable for white as the partial configuration C2.
Input
The first line of the input contains an integer, the number of test cases. A test case includes one line with Test N, where N is the current test case number followed by eight lines, specifying the two partial configurations C1 and C2 in this order. Each configuration is specified by four lines.
The first line of the partial configuration contains three numbers: n1, n2, n3 denoting the heights of the three towers of the partial configuration (0 ≤ n1, n2, n3 ≤ 50). The second line contains n1 letters (B or W) separated by spaces describing the first tower. The third line contains n2 letters separated by spaces describing the second tower. The fourth line contains n3 letters separated by spaces describing the third tower. A letter W denotes a white cube and the letter B denotes a black cube. Each tower is described in the bottom-to-top order.
Output
For each test case, print on a separate line the test case number and Yes if C1 is at least as favorable for white as the partial configuration C2, and No otherwise.
Sample Input

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

Sample Output

Test 1: Yes
Test 2: No

Source
MIT Programming Contest 2005
 
 
정밀도 문제를 고려하다
논문 봐!

#include<iostream>
#include<cstdlib>
#include<stdio.h>
using namespace std;
int tt[55];
long long  dfs(int n)
{
    long long  x=0,k=1;
    int i=1;
    k<<=52;// 
    while(i<=n&&tt[i]==tt[1])
    {
        if(tt[i]==1)
        x+=k;
        else x-=k;
        i++;
    }
    k>>=1;
    while(i<=n)
    {
        if(tt[i]==1)
        x=x+k;
        else x=x-k;
        i++;
        k>>=1;
    }
    return x;
}
void solve(int n)
{
     for(int i=1;i<=n;i++)
    {
            char c;
            cin>>c;
            if(c=='W') tt[i]=1;
            else tt[i]=0;

    }

}
int main()
{
    int t,d;
    char str[10];
    int a[55];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%d",str,&d);
        char c;
        int n1,n2,n3;
        //cout<<str<<" "<<d<<endl;
        scanf("%d%d%d",&n1,&n2,&n3);
        long long ans1=0,ans2=0;
        solve(n1);ans1+=dfs(n1);
        solve(n2);ans1+=dfs(n2);
        solve(n3);ans1+=dfs(n3);
        scanf("%d%d%d",&n1,&n2,&n3);
        solve(n1);ans2+=dfs(n1);
        solve(n2);ans2+=dfs(n2);
        solve(n3);ans2+=dfs(n3);
        printf("%s %d: ",str,d);
     //  cout<<ans1<<" "<<ans2<<endl;
        if(ans1>=ans2) puts("Yes");
        else puts("No");
    }
}