No.2723 Fortune-telling by Flowers
MasKoaTS
p-adic
ygussanyProblem Statement
You are given a string $S$ of length $N$ consisting only of K, P, and -. Below, the $i$-th $(1 \leq i \leq N)$ character from the beginning of $S$ is denoted by $S_{i}$.
It is also guaranteed that, for at least $1$ of the characters contained in $S$, that character and - are not equal.
Koa and Pache will now play a game. Starting with Koa, they alternately perform the following operation.
First, choose $1$ pair of integers $(x, y)$ satisfying all of the following conditions.
$1 \leq x \leq y \leq N$
For every integer $i$ satisfying $x \leq i \leq y$, $S_{i}$ and
-are not equal.There exists an integer $i$ satisfying $1 \leq i < x$ or $y < i \leq N$ such that $S_{i}$ and
-are not equal.Next, for each integer $i$ satisfying $x \leq i \leq y$, replace $S_{i}$ with
-.
If there is no pair of integers $(x, y)$ that can be chosen in operation 1 above, the game ends.
It can be proved that, when the game ends, there exists exactly one integer $i$ satisfying $1 \leq i \leq N$ such that $S_{i}$ and
- are not equal.
Based on this $S_{i}$, the result of the game is determined as follows.
If $S_{i}$ is
K, Koa wins; otherwise, Pache wins.
Determine who wins when both players play optimally.
$T$ test cases are given; find the answer for each of them.
Constraints
$1 \leq T \leq 10^{5}$
$1 \leq N \leq 5 \times 10^{5}$
$S$ is a string of length $N$ consisting only of
K,P, and-For at least $1$ of the characters contained in $S$, that character and
-are not equalThe sum of $N$ given in $1$ input is at most $5 \times 10^{5}$
All inputs other than $S$ 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$ $S$
Output
Print the answers, $1$ per line, for a total of $T$ lines.
On line $i$ $(1 \leq i \leq T)$, for the game played on the $i$-th test case, if Koa wins, print K; if Pache wins, print P.
Sample
Sample 1
Input
4 1 K 9 -PKP-P-KK 3 PPK 10 K-PK---P-K
Output
K P K K
First, in the $1$st test case, Koa has a winning strategy. In this case, the operations proceed as follows.
There is no pair of integers $(x, y)$ that Koa can choose. At this point, $S$ is
K, so Koa wins.
Next, in the $2$nd test case, Pache has a winning strategy. For example, the operations proceed as follows.
Koa chooses $(x, y) = (3, 4)$ and replaces $S_{3}, S_{4}$ with
-. Now $S$ becomes-P---P-KK.Pache chooses $(x, y) = (9, 9)$ and replaces $S_{9}$ with
-. Now $S$ becomes-P---P-K-.Koa chooses $(x, y) = (2, 2)$ and replaces $S_{2}$ with
-. Now $S$ becomes-----P-K-.Pache chooses $(x, y) = (8, 8)$ and replaces $S_{8}$ with
-. Now $S$ becomes-----P---.There is no pair of integers $(x, y)$ that Koa can choose. At this point, $S$ is
-----P---, so Pache wins.
Finding the answers for the remaining test cases in the same way gives the sample output above.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。