問題一覧 > 通常問題

No.1716 Bonus Nim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : nok0nok0 / テスター : Kite_kumaKite_kuma zkouzkou 👑 ygussanyygussany
12 ProblemId : 6579 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-16 18:47:00

問題文

Alice と Bob でゲームをします。

最初 $N$ 個の山があり、$i$ 番目の山には $A_i$ 個の石が置いてあります。

Alice から始めて $2$ 人は交互に以下の操作のいずれかを選択して繰り返します。

  1. 石が $1$ つ以上残っているような山を $1$ つ選ぶ。選んだ山に $X$ 個の石があるとき、 $1$ 個以上 $X$ 個以下の任意の個数の石をその山から取り除く。全ての石を取り除いた場合、すなわち $X$ 個の石を取り除いた場合、ボーナスとしてコインを $1$ 枚得る。
  2. 持っているコインを $1$ 枚捨てる。

先に操作ができなくなったプレイヤーが負けとなります。

はじめ、 Alice も Bob もコインを持っていません。Alice も Bob も自分が勝つために最適な行動をするとき、どちらが勝つか判定してください。

一つの入力ファイルにつき、 $T$ 個のテストケースに答えてください。

制約

  • 入力は全て整数である。
  • $1 \le T\le 2 \times 10^5$
  • $1 \le N \le 2 \times 10^5 $
  • $1 \le A_i\le 10^9 $
  • $1$ つの入力ファイルについて、 $N$ の総和は $5\times 10^5$ 以下である。

入力

入力は以下の形式で標準入力から与えられる。

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられる。

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

$T$ 行出力してください。$i\ (1\le i \le T)$ 行目には $i$ 番目のテストケースの勝者が Alice なら Alice、 Bob なら Bob と出力してください。

サンプル

サンプル1
入力
2
1
3
2
1 1
出力
Alice
Bob

例えば、 $2$ 番目のゲームにおいて以下のようなシナリオが考えられます。

  • Alice が操作 $1$ を行い $1$ 番目の山を選択して石を $1$ つ取り除く。 $1$ 番目の山の石が無くなったのでコインを $1$ 枚得る。
  • Bob が操作 $1$ を行い $2$ 番目の山を選択して石を $1$ つ取り除く。$2$ 番目の山の石が無くなったのでコインを $1$ 枚得る。
  • Alice が操作 $2$ を行いコインを $1$ 枚捨てる。
  • Bob が操作 $2$ を行いコインを $1$ 枚捨てる。
  • Alice はこれ以上操作が行えないので敗北する。Bob の勝利である。

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