問題一覧 > 通常問題

No.601 Midpoint Erase

レベル : / AI推定難易度 : 650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 240
作問者 : nanae / テスター : kopricky
お気に入りにしたユーザー ProblemId : 1994 / 自分の提出
問題文最終更新日: 2026-06-28 13:24:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2017 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。