分数: 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