No.2721 "Don't say N" Game

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 168
作問者 :

MasKoaTS / テスター : 👑

p-adic 👑

ygussany

0 ProblemId : 10173 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-03-30 17:19:19

正整数 $N$ が与えられます。

これから、コアさんとパチェさんがゲームを行います。コアさんから始めて、次の操作を交互に行います。

両者のうち、先に $N$ を宣言した方を負けとします。

両者が最善を尽くしたとき、どちらが勝つか判定してください。

$T$ 個のテストケースについて答えを求めてください。

入力は次の形式で与えられます。

 $T$ 
 $\mathrm{case}_{1}$ 
 $\mathrm{case}_{2}$ 
   $\vdots$ 
 $\mathrm{case}_{T}$

各テストケースは次の形式で与えられます。

$N$

答えを $1$ 行ずつ合計 $T$ 行に出力してください。

$i$ $(1 \leq i \leq T)$ 行目には、 $i$ 個目のテストケースについてゲームを行ったときにコアさんが勝つならば K を、パチェさんが勝つならば P を出力してください。

P
K
K
P

まず、 $1$ つ目のテストケースでは、先手のコアさんが宣言できる整数は $1$ のみなので、パチェさんが必勝です。

続いて、 $2$ つ目のテストケースではコアさんが必勝です。例えば、次のように操作を行います。

$6$ の正の約数のうち、コアさんが宣言可能なものは $1, 2, 3, 6$ の $4$ 個である。この中からコアさんは $2$ を選んで宣言する。
$6$ の正の約数のうち、パチェさんが宣言可能なものは $1, 3, 6$ の $3$ 個である。この中からパチェさんは $3$ を選んで宣言する。
$6$ の正の約数のうち、コアさんが宣言可能なものは $1, 6$ の $2$ 個である。この中からコアさんは $1$ を選んで宣言する。
$6$ の正の約数のうち、パチェさんが宣言可能なものは $6$ のみである。この中からパチェさんは $6$ を選んで宣言する。
パチェさんが先に $6$ を宣言したことにより、コアさんの勝ちとなる。

なお、上の操作はあくまでも両者が最善を尽くした場合に行う操作の一例であることに注意してください。

厳密には、このテストケースにおいてパチェさんがどのように行動したとしても、コアさんが適切に行動することにより、
必ずコアさんの勝ちでゲームが終了することに注意してください。

例えば、次のように操作を行ってコアさんが勝つ場合もあり得ます。

$6$ の正の約数のうち、コアさんが宣言可能なものは $1, 2, 3, 6$ の $4$ 個である。この中からコアさんは $3$ を選んで宣言する。
$6$ の正の約数のうち、パチェさんが宣言可能なものは $1, 2, 6$ の $3$ 個である。この中からパチェさんは $1$ を選んで宣言する。
$6$ の正の約数のうち、コアさんが宣言可能なものは $2, 6$ の $2$ 個である。この中からコアさんは $2$ を選んで宣言する。
$6$ の正の約数のうち、パチェさんが宣言可能なものは $6$ のみである。この中からパチェさんは $6$ を選んで宣言する。
パチェさんが先に $6$ を宣言したことにより、コアさんの勝ちとなる。

残りのテストケースについても同様に答えを求めると、上の出力例のようになります。

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