BG2 - Binary Game Reloaded
Alice and Bob always loves to play different games. One day, they were not finding any game to play and so they were feeling disappointed. Suddenly, they found a book in their room with a binary number written onto it, the length of which was not longer than 100000. Then, They formulate the game rule, say "Binary Game".
In this game, the first player chooses a pair of indexes of the binary string and reverses the substring generated by it, so that the string will become lexicographically minimum among all possible selections of indices pairs, and give it to second player. Then, second player do the same thing on the string and give it back to first player. This process continues until there is no way to make binary string lexicographically smaller than before. The player who can not make q move loses the game.
Today, Alice and Bob are playing the Binary Game in their room. Suddenly, you enter into their room. Now, Your task is to determine the winner of the game if both of them play in well disciplined manner and the first player of the game is Alice.
Input
Input starts with an integer T (1<=T<=30), denoting the number of test cases.
Each case contains a binary string probably with leading zeros, which is a binary number in the range of 100000 bit number.
Output
For each case of input, output the name of the winner of the game.
Example
Input: 3 00 01 10 Output: Bob Bob Alice
hide comments
anonymous:
2017-04-11 14:08:29
Reverse in this problem means reversing the order of characters. It is _not_ a bit complement.
|
|
wisfaq:
2017-04-11 12:36:21
Only if the input is a one character string Alice can't make a move, so she loses
|
|
Vipul Srivastava:
2017-04-10 14:20:19
In the first case I can understand Bob is the winner as Alice can't make a move but how is the second case winner not Alice. She can choose substring [2,2] and reverse it and the new string will be '00' and Bob can't make a move now. |
|
wisfaq:
2017-04-10 12:02:23
As far as I can see Alice is the winner in all cases. |
Added by: | BISHAL GAUTAM |
Date: | 2017-04-09 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Big Version of DevSkill Coding Contest-14(https://www.devskill.com/CodingProblems/ViewProblem/282) |