No.2814 Block Game
タグ : / 解いたユーザー数 29
作問者 :
![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)
問題文
AliceとBobが、長さ $N$ の数列 $A$ を使ってゲームをしています。はじめ、$1\leq i\leq N$ なる任意の $i$ について $A_i=-1$ です。
AliceとBobは、Aliceから始めて交互に以下の一連の操作を行います。
- $A_i=-1$ なる $i$ が存在しないなら、ゲームを終了する。
- 存在するならば、まず、$1$ 以上 $N$ 以下の整数 $x$ と、$A_i=-1$ なる $i$ をひとつ選ぶ。ただし、$x$ が $A$ に含まれていてはならない。
- その後、$A_i$ を $x$ で置き換える。
ゲームを終了した後、数列 $A$ に、$N-1$ 回以下の操作を行います。
- 操作開始時点での $A$ の長さを $n$ として、$A$ を $(A_1+A_2,A_2+A_3,\dots,A_{n-1}+A_{n})$ に置き換える。
最終的に $A$ にはただ一つの整数が残ることが示せます。その整数を $X$ とします。
このゲームの勝敗は、Odd
または Even
である文字列 $S$ を用いて以下のように判定されます。
- $S$ が
Odd
のとき、$X$ が奇数であればAliceの勝利、偶数であればBobの勝利 - $S$ が
Even
のとき、$X$ が偶数であればAliceの勝利、奇数であればBobの勝利
両者が自身の勝利を目指して最適に行動するとき、勝利するのはAliceとBobのどちらでしょうか。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- $1\leq T\leq 2\times 10^{5}$
- $1\leq N\leq 10^{18}$
- $S$ は
Odd
またはEven
- $T,N$ は整数
入力
$T$ $\text{testcase}_1$ $\text{testcase}_2$ $\vdots$ $\text{testcase}_T$
各テストケースは以下の形式で与えられる。
$N$ $S$
出力
$T$ 行出力してください。
$i$ 行目には、第 $i$ テストケースについて、Aliceが勝利するなら Alice
を、Bobが勝利するならBob
を出力してください。
サンプル
サンプル1
入力
1 3 Even
出力
Alice
この入力例では、$1$ ケースのみ与えられています。
たとえば、このゲームは以下のように進行します。
- はじめ、$(A_1,A_2,A_3)=(-1,-1,-1)$ である。
- Aliceが $x=2,i=2$ を選んで操作を行う。$(A_1,A_2,A_3)=(-1,2,-1)$ となる。
- Bobが $x=1,i=3$ を選んで操作を行う。$(A_1,A_2,A_3)=(-1,2,1)$ となる。
- Aliceが $x=3,i=1$ を選んで操作を行う。$(A_1,A_2,A_3)=(3,2,1)$ となる。
- Bobが宣言できる $i$ が存在しないので、ゲームを終了する。
- $A$ に対して操作を行う。$1$ 回目の操作で $A=(A_1+A_2,A_2+A_3)=(5,3)$ となり、$2$ 回目の操作で $A=(A_1+A_2)=(8)$ となる。よって、$X=8$ となる。
- $S$ が
Even
であり、$X$ が偶数なので、Aliceが勝利する。
これは両者が最適に行動しているとは限りませんが、両者が最適に行動しても勝者はAliceであることが示せます。
この進行において、たとえば、Aliceが $2$ 回目の操作で $x=1$ を選ぶことは不正です。$A_3=1$ であり、すでに $1$ が含まれているからです。
また、Bobが $1$ 回目の操作で $i=2$ を選ぶことも不正です。$A_2=2$ であり、$-1$ でないからです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。