DCEPC807 - Bit by Bit

no tags 

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:

  1. Let F(n) denotes the total no. of set bits in binary representation of numbers from 0 to (2^n) -1.
  2. Each player plays alternatively until the game ends and one of them wins the game.
  3. 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”.
  4. The game ends when F(x) is a power of 2. (0 is also a power of 2).
  5. The player with no move loses the game and so other player wins the game.
  6. Alice starts the game always.
  7. 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: 2015-06-09 14:12:58

Awesome problem!!!

|RAMSDEN|: 2014-08-08 21:00:55

Really Amazing problem:)
Recursion with memoization is far superior than precomputation in this problem
reduced time from 21s to 0.19 s
just by changing precomputation to recursion

Mitch Schwartz: 2014-04-24 17:11:07

@Aadithya U: Optimal or perfect play is a common (and well-defined) 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: 2014-04-24 17:37:48
Aadithya U: 2014-04-24 07:53:55

what does "they play optimally" mean? can anyone say that with an example ??

technophyle: 2013-06-29 08:00:24

The problem is correct. Read the problem carefully that game ends when a player is not able to make a move

Enjoy the problem :D

Mitch Schwartz: 2012-08-28 08:18:17

@Code for food: F(10) does not equal 2. Read the problem statement carefully.

Code for food: 2012-08-28 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.

@Mitch: My bad. I got it now. Thanks.

Last edit: 2012-08-28 06:03:27
Darko Aleksic: 2012-08-28 08:18:17

In the first case game is over before Alice can make a move.

ɥsǝןǝǝu: 2012-08-28 08:18:17

i think in both cases Alice wins........please someone explain the output..

Code for food: 2012-08-28 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: 2012-08-27 07:57:50

Added by:dce coders
Date:2012-08-19
Time limit:0.845s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C CPP C++ 4.3.2 CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem