No.2813 Cookie
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 :
warabi0906
/ テスター :
hirayuu_yc
Magentor
highlighter
Yoyoyo8128
zeta7532
fact493
タグ : / 解いたユーザー数 51
作問者 :
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![highlighter](https://pbs.twimg.com/profile_images/1707374069132439552/b_BWx6c8.png)
![fact493](https://pbs.twimg.com/profile_images/1641449306531192836/GjfyenV1.jpg)
問題文最終更新日: 2024-07-19 21:19:33
問題文
Aliceが $N$ 枚のクッキーを焼き、皿の上に置きました。
$i$ 枚目のクッキーの大きさは $A_i$ です。
そのクッキーを使って、AliceとBobがゲームをします。
Aliceから交互に次の二つの操作の内どちらかを行い、操作ができなかった方が負け、負けなかった方の勝ちです。
- 皿の上にあるクッキーを一つ選び、食べる(皿の上からなくなる)。
-
皿の上にある大きさ $2$ 以上のクッキーを一つ選ぶ。(その大きさを $c$ と置く。)
そのクッキーを割る。
つまり、 $2$ 以上の整数 $k$ と $\sum _ {i=1} ^ {k} {c' _ i} = c$ を満たす正整数組 $(c' _ {1} , c' _ {2} ... c' _ {k})$ を選択し、皿の上から選んだクッキーを削除したのち、 $1 \leq i \leq k$ について大きさ $c' _ i$ のクッキーをを皿の上に追加する。
二人が自分が勝利するために最適に行動した場合、どちらが勝ちますか。
以上の問題を $T$ ケースについて解いてください。
入力
$T$
$\text{case}_{1}$
$\text{case}_{2}$
⋮
$\text{case}_{T}$
それぞれのケースは次の形式で与えられる。
$N$ $A _ 1 A _ 2 A _ 3 ... A _ N$
- 入力は全て整数
- $1 \leq N,T \leq 2×10^5$
- $1 \leq A _ i \leq 2 \times 10^9 (1 \leq i \leq N)$
- 全てのテストケースの $N$ の和は $2 × 10^5$以下
出力
それぞれのケースについて、次のように回答してください。
Aliceが勝利するならばAlice
、Bobが勝利するならBob
と一行で出力してください。
その後、改行してください。
サンプル
サンプル1
入力
3 1 1 2 5 5 7 44 65 32 7 100 87 91
出力
Alice Bob Alice
一つ目のケースについて、皿の上にある唯一のクッキーを食べてしまえばAlice
の勝利です。
二つ目のケースについて、Bob
はAlice
の操作を真似ることで勝利できます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。