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
beatsS
;P
beatsR
;S
beatsP
.
Constraints
- 1 \leq n,k \leq 100
- s is a string of length n consisting of
R
,P
, andS
.
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