問題一覧 > 通常問題

No.1506 Unbalanced Pocky Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 131
作問者 : oliverx3oliverx3 / テスター : nok0nok0 遭難者遭難者 yuto1115yuto1115
6 ProblemId : 6261 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-14 11:30:36

問題文

正整数からなる長さ $N$ の数列 $A$ が与えられます。数列の $i\ (1 \leq i \leq N)$ 番目の要素は $A_i$ です。

Alice と Bob はこの数列でゲームをします。$2$ 人は以下の操作を、$A$ が空になるまで毎ターン交互に行います。

  • 数列の末尾の要素を $k$ とする。プレイヤーは末尾の要素を $0$ 以上 $k$ 未満の整数に変える。$0$ になった要素は数列から消える。

自分の手番で操作ができなくなったプレイヤーの負けです。

Alice が先手で、$2$ 人とも最適にプレイすると仮定したとき、どちらのプレイヤーが勝つか判定してください。

制約

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9\ (1 \leq i \leq N)$
  • 入力は全て整数

入力

$N$
$A_1\ A_2\ \cdots\ A_N$

出力

Alice が勝つとき Alice と、Bob が勝つとき Bob と出力してください。

サンプル

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

ゲームは、例えば以下のように進行します:

  • Alice が末尾の要素を $1$ にする。$A=(2,\ 1,\ 1)$ になる。
  • Bob が末尾の要素を $0$ にする。$A=(2,\ 1)$ になる。
  • Alice が末尾の要素を $0$ にする。$A=(2)$ になる。
  • Bob が末尾の要素を $1$ にする。$A=(1)$ になる。
  • Alice が末尾の要素を $0$ にする。$A=()$ になる。

この場合、Bob はこれ以上操作をすることができないので、Alice の勝ちです。

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

サンプル3
入力
6
3 1 4 1 5 9
出力
Alice

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