DCEPC807  Bit by Bit
Alice and Bob play an interesting game. They start with a number “n” and follow some rules until the game ends. The rules for the game are:
 Let F(n) denotes the total no. of set bits in binary representation of numbers from 0 to (2^n) 1.
 Each player plays alternatively until the game ends and one of them wins the game.
 In each turn a player either unsets a single set bit from binary representation of “n” or unsets 2 consecutive set bits from the binary representation of “n”. Let’s call the resulting number after such move as “x”.
 The game ends when F(x) is a power of 2. (0 is also a power of 2).
 The player with no move loses the game and so other player wins the game.
 Alice starts the game always.
 Both of them play optimally.
Given “n” can you predict the winner of the game?
Input
First line contains T, the no. of test cases.
Next T lines contains one integer per line, “n” (quotes for clarity).
Output
Output T lines, each containing either “Alice” if Alice wins the game or “Bob” if Bob wins the game.
Constraints
1<=T<=10
0<=N<=10^6
Example
Input: 2
4
10
Output: Bob
Alice
hide comments
Anubhav Gupta:
20150609 14:12:58
Awesome problem!!! 

RAMSDEN:
20140808 21:00:55
Really Amazing problem:)


Mitch Schwartz:
20140424 17:11:07
@Aadithya U: Optimal or perfect play is a common (and welldefined) concept in game theory, but you don't need to study game theory to understand it. You probably know that the outcome of tic tac toe is known in advance when both players don't make any mistakes. It's the same idea. Last edit: 20140424 17:37:48 

Aadithya U:
20140424 07:53:55
what does "they play optimally" mean? can anyone say that with an example ?? 

technophyle:
20130629 08:00:24
The problem is correct. Read the problem carefully that game ends when a player is not able to make a move


Mitch Schwartz:
20120828 08:18:17
@Code for food: F(10) does not equal 2. Read the problem statement carefully. 

Code for food:
20120828 08:18:17
@Drako: The second game is also over before Alice can make a move. 10 (base 10) = 1010 (base 2). So F(10) = 2 = 2^1. Rule 4 says that the game ends when F(x) is a power of 2.


Darko Aleksic:
20120828 08:18:17
In the first case game is over before Alice can make a move. 

ɥsǝןǝǝu:
20120828 08:18:17
i think in both cases Alice wins........please someone explain the output.. 

Code for food:
20120828 08:18:17
Can you explain the examples? In the first case, Alice can only take 1 bit and the game ends (rule 4). In the second case, Alice can only take 1 bit also and the game ends (rule 4) again. How come Bob wins the first game and Alice the second? Last edit: 20120827 07:57:50 
Added by:  dce coders 
Date:  20120819 
Time limit:  0.845s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ASM32GCC MAWK BC CCLANG C CPP C++ 4.3.2 CPP14CLANG CPP14 COBOL COFFEE DDMD DCLANG DART ELIXIR FANTOM FORTH GOSU GRV JAVA JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own Problem 