N - Chocolate Game
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 H cm、横 W cm の長方形のチョコレートがあります。
Alice と Bob が次の操作を交互に繰り返します。- チョコのいずれかの辺に平行な直線でチョコを (それぞれが正の面積になるように) 切断し、片方を食べる。 ただし、残されたチョコの辺の長さは全て正整数であり、かつ面積が K \mathrm{cm}^2 以上でなければならない。
Alice が先手で、操作ができなくなったほうが負けです。勝つのはどちらでしょうか。
Q 個のテストケースに対して答えてください。
制約
- 1 \le Q \le 2\times 10^5
- 1 \leq H,W \leq 10^9
- 1 \le K \le H\times W
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q H_1 W_1 K_1 H_2 W_2 K_2 \vdots H_Q W_Q K_Q
出力
Q 行出力せよ。 i\ (1 \le i \le Q) について、 i 行目には、 i ケース目について Alice が勝利するならば Alice と、 Bob が勝利するならば Bob と出力せよ。
入力例 1
3 3 4 3 2 2 3 1000 800 3000
出力例 1
Alice Bob Alice
1 つ目のケースについて、例えば次のような進行が考えられます。
- Alice が縦 3 cm、横 3 cm となるようチョコレートを切断し、残りを食べる。残ったチョコレートの面積は 9 \mathrm{cm}^2 である。
- Bob が縦 2 cm、横 3 cm となるようチョコレートを切断し、残りを食べる。残ったチョコレートの面積は 6 \mathrm{cm}^2 である。
- Alice が縦 1 cm、横 3 cm となるようチョコレートを切断し、残りを食べる。残ったチョコレートの面積は 3 \mathrm{cm}^2 である。
- Bob はどのように切断しても残りのチョコレートの面積を 3 \mathrm{cm}^2 以上にすることはできないため、Alice の勝ちとなる。