No.2721 "Don't say N" Game
タグ : / 解いたユーザー数 166
作問者 :
MasKoaTS
/ テスター :
👑 
p-adic
ygussany
問題文
正整数 $N$ が与えられます。
これから、コアさんとパチェさんがゲームを行います。コアさんから始めて、次の操作を交互に行います。
$N$ の正の約数のうち $1$ つを選んで宣言する。ただし、この操作の前に既に宣言された整数は宣言できない。
両者のうち、先に $N$ を宣言した方を負けとします。
両者が最善を尽くしたとき、どちらが勝つか判定してください。
$T$ 個のテストケースについて答えを求めてください。
制約
$1 \leq T \leq 1000$
$1 \leq N \leq 1000$
入力はすべて整数
入力
入力は次の形式で与えられます。
$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
$\vdots$
$\mathrm{case}_{T}$
各テストケースは次の形式で与えられます。
$N$
出力
答えを $1$ 行ずつ合計 $T$ 行に出力してください。
$i$ $(1 \leq i \leq T)$ 行目には、$i$ 個目のテストケースについてゲームを行ったときにコアさんが勝つならば K を、パチェさんが勝つならば P を出力してください。
サンプル
サンプル1
入力
4 1 6 23 961
出力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。