PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
There are X biscuits and Y cakes.
Alice and Bob take turns eating them.
On their turn, a player must do one of the following:
- Eat one biscuit.
- Eat one cake and one biscuit.
- Eat one cake, but add one biscuit to the pile.
The winner is whoever makes the last move.
Who wins with optimal play?
EXPLANATION:
The key to solving this problem is noticing that there’s actually not really a choice the players can make!
Observe that no matter what move the current player makes, the number of biscuits available will definitely either increase by 1 or decrease by 1.
In particular, this means its parity will always change: if it was previously even, it becomes odd; and if it was odd, it becomes even.
The “final state” occurs when there are 0 biscuits and 0 cakes left.
This means the final state must have an even number of biscuits.
This uniquely determines the parity of moves that will have been made to reach the final state (no matter how it is reached).
Now, because Alice makes moves 1, 3, 5, 7, \ldots and Bob makes moves 2, 4, 6, \ldots, the person who made the last move is also uniquely determined.
Thus, we see that:
- If X is odd, an odd number of moves must be made to reach the final state.
Thus, the winner is Alice. - If X is even, an even number of moves must be made to reach the final state.
Thus, the winner is Bob.
(For a more constructive argument: note that if X is initially odd, then X will always be odd on Alice’s turn and so she will always have a move to play (eating one biscuit), and hence cannot lose. If X is initially even, the same applies but to Bob instead.)
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
x, y = map(int, input().split())
print('Alice' if x%2 == 1 else 'Bob')