首页 » 博弈论 » 正文

2104. Game with a Strip

2104. Game with a Strip

来源:http://acm.timus.ru/problem.aspx?space=1&num=2104
Time limit: 2.0 second
Memory limit: 64 MB

There is a strip 1 × n with two sides. Each square of the strip (their total amount is 2n, n squares on each side) is painted in one of two colors (let’s call them A and B). Alice and Bob play a game. Alice makes the first turn. On each turn, a player can bend the strip in half with the fold passing on the divisions of the squares (i.e. the turn is possible only if the strip has an even length). Bending the strip can be done either inwards or outwards. If the strip has become completely one color after the next turn, then the winner is the player whose color is it (A refers to Alice, B to Bob). If the current player has no legal moves, but no one has won, the game ends with a draw.

Who will win if both players play optimally? This means that each player tries to win; if it is not possible, to achieve a draw.

Input

The first line contains an integer n that is the length of the strip (1 ≤ n ≤ 5 · 105).

The next two lines contain two strings of letters “A” and “B” with lengths n, describing two sides of the strip. The letters that are under each other, correspond to the different sides of the same square.

Output

If Alice wins, output “Alice”. If Bob wins, output “Bob”. If the game ends with a draw, output “Draw”.

Samples

input output
4 BBAA BABB Bob
3 AAA BBB Draw
2 AA BB Alice

Notes

In the first example, Alice starts the game with the strip BBAA/BABB. After her turn she can get the strip BB/AA or BB/AB. In both cases, Bob can win by getting the strip B/B.

In the second example, Alice can’t make even the first turn, so the result is a draw.

In the third example, Alice wins by the first move, getting the stripe A/A from the strip AA/BB.

解法

首先确定折到哪不能折了,根据最小的不能折计算如果Alice和Bob折到这里是否1. 必定赢 2. 必定输 3. 一定平局 三种情况,依次的逐渐往大的推,计算面对两个结合Alice和Bob所面对的局面是三个中的哪个,最终到达所给出的局面Alice是赢还是输或者平局。

代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;  
const int maxn = 500100;  
int main(){
    //freopen("in.txt", "r", stdin);  
    int n;  
    while(~scanf("%d", &n)){
        char str1[maxn*2],str2[maxn];  
        scanf("%s %s", str1, str2);  

        int base =n;  
        while(base % 2 == 0){
            base /= 2;  
        }
        strcpy(str1+n, str2);  
        short arr[maxn*2][2];  
        memset(arr, -1, sizeof(arr));  
        for(int i=0; i<2*n; i+=base){
            for(int j=1; j<base; j++){
                if(str1[i+j] != str1[i+j-1]){  //存在两种不同的字符 
                    arr[i/base][0] = arr[i/base][1] = 0;  
                }
            }
            if(arr[i/base][0] == -1 && str1[i] == 'A') arr[i/base][0]=1;  //只有一种字符 
        }
        int temp = 2*n/base;  

        for(int i=0; i<temp; i+=2){
            if(arr[i][0] != arr[i+1][0]){  //两面不一样,平局 
                arr[i/2][0] = arr[i/2][1] = 0;  
            }
            else if(arr[i][0] == 1){  //Alice win
                arr[i/2][0]=1;  arr[i/2][1]=-1;  
            }
            else if(arr[i][0]==-1){  //Bob win
                arr[i/2][0]=-1;  arr[i/2][1]=1;  
            }
            else {
                arr[i/2][0]=0;  arr[i/2][1]=0;  
            }
        }
        temp/=2;  

        while(temp >1){
            for(int i=0; i<temp; i+=2){
                int temp1, temp2;  
                if(arr[i][1] == 1 && arr[i+1][1] == 1){  //Alice will lose.
                    temp1=-1;  
                }
                else if(arr[i][1] == -1 || arr[i+1][1] == -1){  //Alice will win.
                    temp1=1;  
                }
                else {
                    temp1=0;  // Game will draw
                }

                if(arr[i][0] == 1 && arr[i+1][0] == 1){  //Bob will lose. 
                    temp2=-1;  
                }
                else if(arr[i][0] == -1 || arr[i+1][0] == -1){  // Bob will win.  
                    temp2=1;  
                }
                else {
                    temp2=0;  
                }
                arr[i/2][0]=temp1;  arr[i/2][1]=temp2;  
            }
            temp /= 2;
        }

        if(arr[0][0] == 1 ){
            printf("Alice\n");  
        }
        else if(arr[0][0] == -1){
            printf("Bob\n");  
        }
        else printf("Draw\n");  
    }
}

赞 (0)

发表评论