← 返回题目列表

AtCoder · arc109_c

C. 大型RPS锦标赛

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

为了决定石头剪刀布中哪一个最强,我们将举办一场RPS锦标赛。 有 2^k 本次比赛的选手,编号 0 通过 2^k-1。每个玩家都有他/她最喜欢的手牌,他/她将在每场比赛中使用它。

一个字符串 s 长度 n 组成 R, P,和 S 代表玩家最喜欢的手牌。 具体来说,玩家最喜欢的手牌 i 表示为 ((i\text{ mod } n) + 1)- 第一个字符 s; R, P,和 S 分别代表石头、布和剪刀。

对于 l 和 r 这样 r-l 是 2,玩家之间举行的锦标赛的获胜者 l 通过 r-1 将确定如下:

  • If r-l=1 (即只有一名玩家),获胜者是玩家 l.
  • If r-l\geq 2,让 m=(l+r)/2,我们举办了两场比赛,一场是玩家之间的比赛 l 通过 m-1 以及玩家中的另一个 m 通过 r-1。让 a 和 b 成为这些锦标赛的各自获胜者。 a 和 b 然后进行石头剪刀布比赛,这场比赛的获胜者 - 或 a 如果比赛平局 - 是玩家之间举行的锦标赛的获胜者 l 通过 r-1.

找出玩家之间举行的锦标赛获胜者最喜欢的一手牌 0 通过 2^k-1.

注释

  • a\text{ mod } b 表示当 a 除以 b.
  • 石头剪刀布比赛的胜负判定如下:
    • 如果双方玩家选择同一手牌,则比赛平局;
    • R 节拍 S;
    • P 节拍 R;
    • S 节拍 P.

约束

  • 1 \leq n,k \leq 100
  • s 是一个长度为的字符串 n 组成 R, P,和 S.

输入

输入由标准输入按以下格式给出:

n k
s

输出

打印玩家之间举行的锦标赛获胜者最喜欢的手牌 0 通过 2^k-1,如 R, P,或 S.


示例输入 1

3 2
RPS

示例输出 1

P
  • 玩家间锦标赛获胜者最喜欢的一手牌 0 通过 1 is P.
  • 玩家间锦标赛获胜者最喜欢的一手牌 2 通过 3 is R.
  • 玩家间锦标赛获胜者最喜欢的一手牌 0 通过 3 is P.

因此,答案是 P.

   P
 ┌─┴─┐
 P   R
┌┴┐ ┌┴┐
R P S R
``` S ┌───┴───┐ 聚苯乙烯 ┌─┴─┐ ┌─┴─┐ 普瑞斯普 ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ R P S R P S R P ````

示例输入 2

11 1
RPSSPRSPPRS

示例输出 2

P

示例输入 3

1 100
S

示例输出 3

S