﻿ 2104. Game with a Strip | 玄奇博客 # 2104. Game with a Strip

### 2104. Game with a Strip

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.

### 代码

#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];
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] = arr[i/base] = 0;
}
}
if(arr[i/base] == -1 && str1[i] == 'A') arr[i/base]=1;  //只有一种字符
}
int temp = 2*n/base;

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

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

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

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