C - Large RPS Tournament Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

最強のじゃんけんの手を決めるため、トーナメント形式のじゃんけん大会が開催されます。 大会の参加者は 2^k 人で、それぞれ 0 以上 2^k 未満の整数が振られています。どの参加者もそれぞれ得意な手を持っていて、毎試合得意な手のみを出します。

参加者の得意な手は、長さ n の R, P, S からなる文字列 s によって表されます。 具体的には、番号 i の参加者の得意な手は s の (i\text{ mod } 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 未満の参加者による大会の勝者の得意な手を求めてください。

注意

  • a\text{ mod } b は a を b で割ったあまりを表す
  • じゃんけんの勝敗は次のように決められる
    • 同じ手同士はあいこである
    • R は S に勝つ
    • P は R に勝つ
    • S は P に勝つ

制約

  • 1 \leq n,k \leq 100
  • s は R, P, S のみからなる長さ n の文字列

入力

入力は以下の形式で標準入力から与えられる。

n k
s

出力

大会の勝者の得意な手を R か P か S で出力せよ。

入力例 1

3 2
RPS

出力例 1

P
  • 番号が 0 以上 2 未満の参加者による大会の勝者の得意な手は P です。
  • 番号が 2 以上 4 未満の参加者による大会の勝者の得意な手は R です。
  • 番号が 0 以上 4 未満の参加者による大会の勝者の得意な手は P です。

よって、答えは P となります。

   P
 ┌─┴─┐
 P   R
┌┴┐ ┌┴┐
R P S R

入力例 2

11 1
RPSSPRSPPRS

出力例 2

P

入力例 3

1 100
S

出力例 3

S

Score : 500 points

Problem Statement

To decide which is the strongest among Rock, Paper, and Scissors, we will hold an RPS tournament. There are 2^k players in this tournament, numbered 0 through 2^k-1. Each player has his/her favorite hand, which he/she will use in every match.

A string s of length n consisting of R, P, and S represents the players' favorite hands. Specifically, the favorite hand of Player i is represented by the ((i\text{ mod } n) + 1)-th character of s; R, P, and S stand for Rock, Paper, and Scissors, respectively.

For l and r such that r-l is a power of 2, the winner of the tournament held among Players l through r-1 will be determined as follows:

  • If r-l=1 (that is, there is just one player), the winner is Player l.
  • If r-l\geq 2, let m=(l+r)/2, and we hold two tournaments, one among Players l through m-1 and the other among Players m through r-1. Let a and b be the respective winners of these tournaments. a and b then play a match of rock paper scissors, and the winner of this match - or a if the match is drawn - is the winner of the tournament held among Players l through r-1.

Find the favorite hand of the winner of the tournament held among Players 0 through 2^k-1.

Notes

  • a\text{ mod } b denotes the remainder when a is divided by b.
  • The outcome of a match of rock paper scissors is determined as follows:
    • If both players choose the same hand, the match is drawn;
    • R beats S;
    • P beats R;
    • S beats P.

Constraints

  • 1 \leq n,k \leq 100
  • s is a string of length n consisting of R, P, and S.

Input

Input is given from Standard Input in the following format:

n k
s

Output

Print the favorite hand of the winner of the tournament held among Players 0 through 2^k-1, as R, P, or S.

Sample Input 1

3 2
RPS

Sample Output 1

P
  • The favorite hand of the winner of the tournament held among Players 0 through 1 is P.
  • The favorite hand of the winner of the tournament held among Players 2 through 3 is R.
  • The favorite hand of the winner of the tournament held among Players 0 through 3 is P.

Thus, the answer is P.

   P
 ┌─┴─┐
 P   R
┌┴┐ ┌┴┐
R P S R

Sample Input 2

11 1
RPSSPRSPPRS

Sample Output 2

P

Sample Input 3

1 100
S

Sample Output 3

S