No.3258 Xor Division Game
タグ : / 解いたユーザー数 23
作問者 :
Iroha_3856
/ テスター :
lif4635
champignon
tikuwa_
問題文
整数列の多重集合 $S$ があります。
始め、$S = \{(F_1, F_2, \ldots, F_N)\}$ です。ここで、$F$ に $0$ は含まれないことが保証されます。
$A \in S$ なる整数列 $A = (A_1, A_2, \ldots, A_K)$ について、$A$ を位置 $i\ (1 \leq i \leq K)$ で分割することを以下の操作を順番に行うことと定義します
- $i \neq 1$ ならば、$S$ に $(A_1 \oplus A_i, A_2 \oplus A_i, \ldots, A_{i-1} \oplus A_i)$ を追加する
- $i \neq K$ ならば、$S$ に $(A_{i+1} \oplus A_i, A_{i+2} \oplus A_i, \ldots, A_K \oplus A_i)$ を追加する
- $S$ から $A$ を $1$ つ削除する
Alice と Bob が $S$ を使って以下のゲームを行います。
-
Alice から始めて、各プレイヤーが交互に以下の操作を行う
- 好きな $A \in S$ なる整数列 $A$ と $1 \leq i \leq |A|$ となる $i$ を選んで、 $A$ を位置 $i$ で分割する
- ただし、操作したあとの $S$ に $0$ が含まれる数列が存在するような操作はしてはならない
両者が最適に行動した時、どちらが勝つかを判定してください。
入力
$N$ $F_1\ F_2\ \ldots\ F_N$
入力は全て以下の制約を満たす
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq F_i < 2^{30}$
- 入力はすべて整数
出力
両者が最適に行動した時、Alice が勝つなら Alice、Bobが勝つなら Bob と出力し、
最後に改行してください。
サンプル
サンプル1
入力
6 1 2 2 1 5 7
出力
Bob
例えば、以下のような進行が考えられます：
始め、$S = \{(1, 2, 2, 1, 5, 7)\}$ です。
Aliceが数列 $A = (1, 2, 2, 1, 5, 7) \in S$ を選び、$A$ を位置 $5$ で分割します。
このあと、$S = \{(1 \oplus 5, 2 \oplus 5, 2 \oplus 5, 1 \oplus 5), (7 \oplus 5)\} = \{(4, 7, 7, 4), (2)\}$ となります。
Bobが数列 $A = (2) \in S$ を選び、$A$ を位置 $1$ で分割します。
このあと、$S = \{(4, 7, 7, 4)\}$ となります。
$0$ を発生させる操作は行えないことから、Aliceはこのとき、操作を行えなくなるので、Aliceの負け、Bobの勝ちです。
Aliceがどのように行動してもBobが適切に操作を行えばBobが勝つので、Bobと出力します。
サンプル2
入力
1 1
出力
Alice
始め、$S = \{(1)\}$ です。
Aliceが数列 $A = (1) \in S$ を選び、$A$ を位置 $1$ で分割します。
このあと、$S = \{\}$ となります。
Bobはこのあと操作は行えないので、Bobの負け、Aliceの勝ちです。
よって、Aliceと出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。