Alice vs Bob Faceoff solution codechef

For Solution
Click Here!
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:

Choose an integer XX such that XX can be expressed as 2Y2Y, Y≥1Y≥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.

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.
Alice vs Bob Faceoff solution codechef

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.
Alice vs Bob Faceoff solution codechef

1≤T≤2∗1051≤T≤2∗105

1≤N≤10181≤N≤1018
Subtasks
 10 points : 1≤N≤201≤N≤20 , 1≤T≤201≤T≤20
 30 points : 1≤N≤1051≤N≤105, 1≤T≤1051≤T≤105
 60 points : 1≤N≤10181≤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.

For Solution
Click Here!