No.2722 Kenken Fight
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.
First, choose $1$ integer $i$ between $1$ and $N$, inclusive.
Next, move by jumping from platform $N + 1$ to platform $i$.
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)$.
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.
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.
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$.
Pache chooses $i = 3$ and jumps through the platforms in the order $7 \to 3 \to 6 \to 7$. Then, she destroys platform $3$.
Koa chooses $i = 4$ and jumps through the platforms in the order $7 \to 4 \to 7$. Then, she destroys platform $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もしくは右上の雲マークをクリックしてアカウントを作成してください。
MasKoaTS