No.1506 Unbalanced Pocky Game
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 163
作問者 :
oliverx3
/ テスター :
nok0
遭難者
yuto1115
タグ : / 解いたユーザー数 163
作問者 :
oliverx3
/ テスター :
nok0
遭難者
yuto1115
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。