問題一覧 > 通常問題

No.1363 [Zelkova Last Tune] 誰がその最後のベルを鳴らすのか?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 26
作問者 : KazunKazun / テスター : tpynerivertpyneriver
0 ProblemId : 5142 / 出題時の順位表
問題文最終更新日: 2021-01-22 17:30:31

注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

問題文

$i=1,\dots,K$ に対して, 色 $i$ のベル が $A_i$ 個だけ場にあり, 色 $i$ の紙には正の整数 $P_i$ が書かれている. Z君とC君が以下の2段階に分かれているゲームをする. ただし, ゲーム開始時には色 $0$ のベルをそれぞれ $X$ 個, $Y$ 個持っている.

  • 第1段階
    C君から先に以下の2つの行動のうち1つを交互に行い, 2人が連続でパスを選択するまで続ける.
    • (自分の手元に色 $0$ のベルが1つでもある場合) 自分の手元に色 $0$ のベルが $B$ 個 $(B>0)$ あるとき, $1$ 以上 $B$ 以下の整数 $m$ を1つ選び, 自分の手元にあるうち $m$ 個の色 $0$ のベル全てを場にあるどのベルとも一致しない色(第1段階で加わった色も含める)で塗り ( $m$ 個ともその色で塗る) , 場に置く. そして, 今塗った色と同じ色の紙に正の整数を1つ書く.
    • パス(何もしない).
    第1段階を終えた際, 2人の手元に残っている全ての色 $0$ のベルを破棄し, 第2段階へ移る. 以下, 場にあるベルの色の種類数を $M$ とする ( $M \geq K$ である).
  • 第2段階
    Z君から先に以下の行動を上から順に交互に行う.
    • 色 $1, \dots, M$ の中から, 壊れていない (後述) ベルが1つ以上存在する色を1つ選ぶ (以下, その選んだ色を色 $D$ とする).
    • 色 $D$ で現在壊れていないベルの個数を $E$ 個 とし, 色 $D$ の紙に書かれた正の整数を $F$ とする. このとき, $1$ 個以上 $\min (E,F)$ 個以下のベルを1回ずつ叩き, 音を鳴らす. ただし, 1回でも叩いたベルは壊れてしまい, 二度と叩けなくなる.
    交互に行っていった際, 最後の壊れていないベルを鳴らした人が勝者になる.

Z君とC君が第1, 第2段階ともに最善に行動した場合, 勝つのはどちらか?

$T$ 個のテストケースに答えよ.

制約

  • $1 \leq T \leq 300$
  • $1 \leq K \leq 10^3$
  • $1 \leq A_i \leq 10^{18}~(i=1,\dots,K)$
  • $1 \leq P_i \leq 10^{18}~(i=1,\dots,K)$
  • $0 \leq X,Y \leq 10^{18}$
  • 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.
$T$
${\rm case}_1$
$\vdots$
${\rm case}_T$
各ケースは以下の形式で与えられる.
$K\ X\ Y$
$A_1 \cdots\ A_K$
$P_1 \cdots\ P_K$

出力

$T$ 行で出力し, $i$ 行目 $(i=1,\dots,T)$ には第 $i$ テストケースでの勝者が Z君ならば Z, C君ならば Cを出力せよ.

サンプル

入力
3
2 0 0
4 3
2 2
1 0 2
1
1
4 1 0
10 20 30 40
2 3 4 5
Z
C
Z

  • [第1テストケースについて] 第1段階は両者とも色 $0$ のベルを持っていないので, 連続でパスして終了する. 第2段階において, Z君が最初に色 $1$ のベルを1個だけ鳴らすことにより, Z君はそれ以降C君が鳴らしたベルとは異なる色のベルを直前に C君が鳴らしたベルの個数と同じだけ鳴らすことを繰り返すと, 必ずZ君が最後のベルを鳴らすことができる.
  • [第2テストケースについて] 第1段階でC君が1個のベルを色2に塗り, 色2の紙に1と書くことにより, C君がかならず勝つ.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。