問題一覧 > 通常問題

No.1506 Unbalanced Pocky Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 168
作問者 : oliverx3 / テスター : nok0 遭難者 yuto1115
8 ProblemId : 6261 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-14 11:30:36

問題文

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

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

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

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

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

制約

  • 1≤N≤2×105
  • 1≤Ai≤109 (1≤i≤N)
  • 入力は全て整数

入力

N
A1 A2 ⋯ AN

出力

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もしくは右上の雲マークをクリックしてアカウントを作成してください。