C - DEC
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
T 個のテストケースについて、以下の問題を解いてください。
3 枚の皿があり、皿 1 には A 枚、皿 2 には B 枚、皿 3 には C 枚のコインが乗っています。これらを用いて Alice と Bob がゲームをします。Alice が先手を取り、2 人で以下の行動を交互に行います。
行動:次の 2 つのうちいずれかを選び、行う。
- 正整数 x を選ぶ。皿 1 と 2 の両方から x 枚ずつコインを取り除く。
- 正整数 x を選ぶ。皿 2 と 3 の両方から x 枚ずつコインを取り除く。
行動ができなかった人が負け、負けなかった人が勝ちます。Alice と Bob のどちらに必勝法があるか判定してください。
制約
- 1\leq T\leq 2\times 10^5
- 1\leq A,B,C\leq 10^9
入力
入力は以下の形式で標準入力から与えられます。
T \mathrm{test}_1 \mathrm{test}_2 \vdots \mathrm{test}_T
ここで、\mathrm{test}_i は i 番目のテストケースの情報を表し、次の形式で与えられます。
A B C
出力
各テストケースに対する答えを改行区切りで順に出力してください。
それぞれのテストケースについて、Alice に必勝法がある場合は Alice
を、Bob に必勝法がある場合は Bob
を出力してください。
入力例 1
4 3 8 4 10 10 10 131 313 131 314159265 358979323 846264338
出力例 1
Alice Alice Bob Alice
例えば、1 番目のテストケースに対しては次のようなゲームの進行が考えられます。
- Alice が皿 1 と 2 の両方から 2 枚ずつコインを取り除く。
- Bob が皿 2 と 3 の両方から 1 枚ずつコインを取り除く。
- Alice が皿 2 と 3 の両方から 2 枚ずつコインを取り除く。
- Bob が皿 2 と 3 の両方から 1 枚ずつコインを取り除く。
- Alice が皿 1 と 2 の両方から 1 枚ずつコインを取り除く。
最終的に皿 2 にのみコインが 1 枚残り、Bob は操作ができなくなります。この進行はあくまで一例であり、必ずしも最適な行動をとっているとは限りませんが、このテストケースでは Alice に必勝法があることが証明できます。