AT_arc109_c [ARC109C] Large RPS Tournament

为了决定最强的“剪刀石头布”手势，将举办一场锦标赛形式的“剪刀石头布”大赛。参赛者共有 $2^k$ 人，每个人都被分配了一个 $0$ 以上小于 $2^k$ 的整数编号。每位参赛者都有自己擅长的手势，并且每场比赛只会出自己擅长的手势。 参赛者的擅长手势由一个长度为 $n$ 的只包含 `R`、`P`、`S` 的字符串 $s$ 表示。具体来说，编号为 $i$ 的参赛者的擅长手势为 $s$ 的第 $(i\bmod n)+1$ 个字符。其中，`R` 表示石头，`P` 表示布，`S` 表示剪刀。 对于满足 $r-l$ 是 $2$ 的幂的 $l,\ r$，当编号在 $l$ 以上 $r$ 未满的参赛者举办比赛时，胜者的决定方式如下： - 当 $r-l=1$（即只有一名参赛者时），胜者为 $l$。 - 当 $r-l\geq 2$ 时，令 $m=(l+r)/2$，分别让编号在 $l$ 以上 $m$ 未满和 $m$ 以上 $r$ 未满的参赛者举办比赛。设两边的胜者分别为 $a$ 和 $b$，则 $a$ 和 $b$ 进行“剪刀石头布”，胜者为最终胜者。如果平局，则 $a$ 获胜。 请输出编号为 $0$ 以上 $2^k$ 未满的参赛者举办比赛时，最终胜者的擅长手势（`R`、`P` 或 `S`）。

输入通过标准输入给出，格式如下： > $n$ $k$ $s$

请输出锦标赛最终胜者的擅长手势（`R`、`P` 或 `S`）。

### 注意 - $a\bmod b$ 表示 $a$ 除以 $b$ 的余数。 - 剪刀石头布的胜负规则如下： - 相同手势为平局。 - `R` 胜 `S`。 - `P` 胜 `R`。 - `S` 胜 `P`。 ### 约束条件 - $1\leq n,k\leq 100$ - $s$ 是只包含 `R`、`P`、`S` 的长度为 $n$ 的字符串。 ### 样例解释 1 - 编号 $0$ 以上 $2$ 未满的参赛者举办比赛时，胜者的擅长手势为 `P`。 - 编号 $2$ 以上 $4$ 未满的参赛者举办比赛时，胜者的擅长手势为 `R`。 - 编号 $0$ 以上 $4$ 未满的参赛者举办比赛时，胜者的擅长手势为 `P`。 因此，答案为 `P`。 ``` P ┌─┴─┐ P R ┌┴┐ ┌┴┐ R P S R ``` 由 ChatGPT 4.1 翻译