No.601 Midpoint Erase
タグ : / 解いたユーザー数 233
作問者 : nanae / テスター : kopricky
問題文
アリスは退屈していたので、暇が潰せそうなスマホゲームを探していました。
その中で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もしくは右上の雲マークをクリックしてアカウントを作成してください。