問題一覧 > 通常問題

No.601 Midpoint Erase

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 233
作問者 : nanaenanae / テスター : koprickykopricky
7 ProblemId : 1994 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-09 09:44:11

問題文

アリスは退屈していたので、暇が潰せそうなスマホゲームを探していました。
その中でMidpoint Eraseというゲームがありました。
そのゲームを開始すると、2次元平面上に$N$個の格子点$(x_i, y_i)$がばらまかれます。
(格子点とは、$x-$座標、$y-$座標がともに整数である点のことです。)
そして、ある2点をタップして選ぶと、その中点もまた格子点であるときのみ、その中点が青く光って、中点をタップすると選んだ2点を消すことができます。
この操作を繰り返してできるだけ多くの点を消してハイスコアを目指すというシンプルなゲームです。
このゲームで点を消していく感覚が気持ちよく、アリスはこのゲームを暇つぶしにそこそこ遊びました。

しかし長く遊んでいるとシンプルすぎて面白味が無く、アリスは少しこのゲームに飽きてきました。
そこで、アリスはこのゲームを使って友達のボブと2人で遊ぶことにしました。
最初はアリスから始めて、ある2点を選んで消して、次はボブのターンになって、また2点を選んで消して、アリスに戻って……
と2人で交互に操作を繰り返していって、消すことのできる2点が存在しなくなったほうが負け、というルールです。

このゲームでアリスもボブも共に最善の行動をしたとすると、どちらが勝つことができるでしょうか?

入力

$N$
$x_1$ $y_1$
$x_2$ $y_2$
...
$x_N$ $y_N$

一行目に最初に平面上に配置される格子点の数$N$が与えらえます。
そして2行目から各格子点の座標$(x_i, y_i)$が半角スペース区切りで与えられます。

制約は以下の通りです。

  • $2 \leq N \leq 10^5$
  • $0 \leq x_i \leq 10^9$
  • $0 \leq y_i \leq 10^9$
  • 各格子点は全て異なる座標に配置される
  • 入力は全て整数で与えられる

出力

もしアリスが勝つなら"Alice"、ボブが勝つなら"Bob"と出力してください(引用符は要りません)

最後に改行してください。

サンプル

サンプル1
入力
4
1 3
2 1
4 7
5 5
出力
Bob

初めはアリスのターンで、このときアリスは(1, 3)と(5, 5)を選んで消すかまたは(2, 1), (4, 7)を選んで消すことができます。 しかしどちらの操作をしても次にボブに残ったほうを消されてしまい、全ての点が消えてしまうのでAliceの負けです。

サンプル2
入力
4
2 5
8 6
3 1
11 2
出力
Bob

初めにアリスのターンですが、不幸なことにどの2点を選んでも中点が格子点になりません。 この場合は最初から「2点を選んで消す」という操作が出来ないのでAliceの負けとなります。

サンプル3
入力
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
出力
Alice

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。