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:

  1. Let F(n) denotes the total number of set bits in binary representation of numbers from 0 to 2n - 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 number 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 ≤ 106

Example

Input:
2
4
10

Output:
Bob
Alice

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

hide comments
2015-06-09 14:12:58 Anubhav Gupta
Awesome problem!!!
2014-08-08 21:00:55 |RAMSDEN|
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
2014-04-24 17:11:07 Mitch Schwartz
@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
2014-04-24 07:53:55 Aadithya U
what does "they play optimally" mean? can anyone say that with an example ??
2013-06-29 08:00:24 technophyle
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
2012-08-28 08:18:17 Mitch Schwartz
@Code for food: F(10) does not equal 2. Read the problem statement carefully.
2012-08-28 08:18:17 Code for food
@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
2012-08-28 08:18:17 Darko Aleksic
In the first case game is over before Alice can make a move.
2012-08-28 08:18:17 ɥsǝןǝǝu
i think in both cases Alice wins........please someone explain the output..
2012-08-28 08:18:17 Code for food
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.