No.601 Midpoint Erase
Problem Statement
Alice was bored, so she was looking for a smartphone game to kill some time.
Among them, she found a game called Midpoint Erase.
When the game starts, $N$ lattice points $(x_i, y_i)$ are scattered on a two-dimensional plane.
(A lattice point is a point whose $x-$coordinate and $y-$coordinate are both integers.)
When you tap to select two points, then only if their midpoint is also a lattice point, the midpoint glows blue, and tapping the midpoint erases the two selected points.
It is a simple game in which you repeat this operation to erase as many points as possible and aim for a high score.
Erasing points in this game felt satisfying, and Alice played it a fair amount to pass the time.
However, after playing for a long time, the game felt too simple to be interesting, and Alice started to get a little tired of it.
So Alice decided to use this game to play with her friend Bob, just the two of them.
Alice goes first and selects two points and erases them, then it is Bob's turn and he selects two points and erases them, then it is back to Alice, and so on...
The two take turns repeating the operation, and the rule is that the player for whom no two erasable points exist loses.
If both Alice and Bob play optimally in this game, who will win?
Input
$N$ $x_1$ $y_1$ $x_2$ $y_2$ ... $x_N$ $y_N$
The first line gives the number $N$ of lattice points initially placed on the plane.
From the second line onward, the coordinates $(x_i, y_i)$ of each lattice point are given, separated by a half-width space.
The constraints are as follows.
- $2 \leq N \leq 10^5$
- $0 \leq x_i \leq 10^9$
- $0 \leq y_i \leq 10^9$
- All lattice points are placed at distinct coordinates
- All input values are integers
Output
Print "Alice" if Alice wins, or "Bob" if Bob wins (without the quotation marks).
Print a newline at the end.
Sample
Sample 1
Input
4 1 3 2 1 4 7 5 5
Output
Bob
The first turn is Alice's, and she can select and erase either (1, 3) and (5, 5), or (2, 1), (4, 7). However, whichever operation she chooses, Bob then erases the remaining pair and all points are gone, so Alice loses.
Sample 2
Input
4 2 5 8 6 3 1 11 2
Output
Bob
The first turn is Alice's, but unfortunately, no matter which two points she selects, the midpoint is not a lattice point. In this case, the operation of selecting and erasing two points cannot be performed from the start, so Alice loses.
Sample 3
Input
16 9 14 85 85 100 21 50 56 75 41 52 84 90 41 70 62 47 75 45 81 28 34 6 66 96 80 92 33 23 44 59 2
Output
Alice
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。