Alice vs Bob Faceoff solution codechef

Alice vs Bob Faceoff solution codechef

Alice and Bob have got an integer NN. They decide to play a game. Alice and Bob make alternating moves: Alice makes the first move, Bob makes the second move, Alice makes the third one, and so on. The game continues until NN becomes 00. The player who is unable to make a move loses.

During each turn a player can make one of the following moves:

  1. Choose an integer XX such that XX can be expressed as 2Y2YY1Y≥1. The chosen XX must also be a factor of NN. After choosing an integer XX which satisfies the mentioned criteria, the player will divide NN by XX.

  2. If Move 11 is not possible , the player will subtract 11 from NN.

Predict the winner of the game if the game is played optimally by both the players.

  • The first line of input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.

  • The first line of each test case contains an integer NN.

Output Format

For each test case, print “Alice” if Alice wins the game else print “Bob”. Print the output without quotes.

  • 1T21051≤T≤2∗105

  • 1N10181≤N≤1018

Subtasks

  • 10 points : 1N201≤N≤20 , 1T201≤T≤20
  • 30 points : 1N1051≤N≤1051T1051≤T≤105
  • 60 points : 1N10181≤N≤1018

Alice vs Bob Faceoff solution codechef

 

2
1
2

Sample Output 1 

Alice
Bob

Explanation

Test case 11: Alice can’t perform the first move, hence she subtracts 1 from NN and NN becomes 00. Bob can’t make a move now.

Test case 11: Alice first divides NN by 22 , after which NN becomes 11. Bob, in the next move decrements NN by 11 after which NN becomes 00 and Alice loses.

Alice vs Bob Faceoff solution codechef

Leave a Reply

Your email address will not be published. Required fields are marked *

*