問題一覧 > 通常問題

No.2722 Kenken Fight

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 102
作問者 : MasKoaTS / テスター : 👑 p-adic ygussany
お気に入りにしたユーザー ProblemId : 10164 / 自分の提出
問題文最終更新日: 2024-03-30 18:01:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 427 (ゲーム問題コンテスト) (順位表) の他の問題:

Problem Statement

There are $N + 1$ platforms floating on a pond, numbered $1, 2, \dots, N + 1$. Here, $N \geq 1$.

Koa and Pache will now play a game. Initially, both are on platform $N + 1$.
Starting with Koa, they alternately perform the following operations.

  1. First, choose $1$ integer $i$ between $1$ and $N$, inclusive.

  2. Next, move by jumping from platform $N + 1$ to platform $i$.

  3. Next, let $x = i$ and repeat the following operation until moving to platform $N + 1$.

    • Add $i$ to $x$, and move by jumping from the platform you are currently on to platform $\min(x, N+1)$.

  4. Finally, destroy platform $i$ by remote control.

Of the two players, the one who first satisfies at least $1$ of the following conditions during the above process loses.

  • At the start of operation 1, among the $N$ platforms $1, 2, \dots, N$, only platform $1$ is not destroyed.

  • In operation 2 or operation 3, the destination platform has already been destroyed.

Determine who wins when both players play optimally.

Solve for $T$ test cases.

Constraints

  • $1 \leq T \leq 10^{5}$

  • $1 \leq N \leq 10^{12}$

  • All input values are integers.

Input

The input is given in the following format.

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

Each test case is given in the following format.

$N$

Output

Output the answers, $1$ per line, for a total of $T$ lines.

On the $i$-th line $(1 \leq i \leq T)$, output K if Koa wins the game for the $i$-th test case, and P if Pache wins.

Sample

Sample 1
Input
4
1
6
2023
1000000000000
Output
P
K
K
K

First, in test case number $1$, Pache has a winning strategy. The operations proceed as follows.

  1. When Koa chooses $i = 1$, among the $1$ platform, platform $1$, only platform $1$ is not destroyed.
    Therefore, Pache wins.

Next, in test case number $2$, Koa has a winning strategy. For example, the operations proceed as follows.

  1. Koa chooses $i = 1$ and jumps through the platforms in the order $7 \to 1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7$. Then, she destroys platform $1$.

  2. Pache chooses $i = 3$ and jumps through the platforms in the order $7 \to 3 \to 6 \to 7$. Then, she destroys platform $3$.

  3. Koa chooses $i = 4$ and jumps through the platforms in the order $7 \to 4 \to 7$. Then, she destroys platform $4$.

  4. Pache chooses $i = 2$ and jumps through the platforms in the order $7 \to 2 \to 4 \to 6 \to 7$.
    In this process, platform $4$ has already been destroyed, so Koa wins.

Finding the answers for the remaining test cases in the same way gives the sample output above.

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