問題一覧 > 通常問題

No.3673 Predicting the Future

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 0.200秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : harurun / テスター : 👑 みうね TKTYI
お気に入りにしたユーザー ProblemId : 13833 / 自分の提出
問題文最終更新日: 2026-09-03 17:01:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 512 BONSAI (順位表) の他の問題:

Note: The execution time limit for this problem is set very strictly.

Problem Statement

You are playing a special version of rock-paper-scissors with a robot named Alice.

This game has 4 types of hands: R, S, P, and X. The outcome for your hand against Alice's hand is determined by the following table.

The rows of the table represent your hand, and the columns represent Alice's hand.

Your hand / Alice's hand R S P X
R Draw Win Draw Lose
S Lose Draw Win Draw
P Draw Lose Draw Win
X Win Draw Lose Draw

Therefore, to beat Alice's hand, you need to play the following hand.

Alice's hand Winning hand
R X
S R
P S
X P

Alice internally holds an unsigned 32-bit integer state.

Initially, state is chosen from the integers between $1$ and $2^{32}-1$, inclusive. You do not know this initial value.

In each round of the game, Alice executes the following pseudocode once to determine her hand.

state ← 1 以上 2^32-1 以下の整数から1つ選ぶ

function generate_random_number():
    state ← state XOR (state << 13)
    state ← state XOR (state >> 17)
    state ← state XOR (state << 5)
    return state

function choose_hand():
    x ← generate_random_number()

    if x mod 4 = 0:
        return 'R'
    else if x mod 4 = 1:
        return 'S'
    else if x mod 4 = 2:
        return 'P'
    else:
        return 'X'

Here, XOR denotes bitwise exclusive OR, << denotes a left bit shift, and >> denotes a right bit shift.

All operations are performed on unsigned 32-bit integers. If the result of an operation exceeds 32 bits, the excess upper bits are truncated.

You have played $100$ rounds with Alice so far and recorded every hand she played.

This record is represented by a string $T$ of length $100$. The $i$-th character of $T$ represents the hand Alice played in the $i$-th round.

Use this record to win all of the upcoming $N$ rounds.

Formally, output a string $U$ of length $N$ satisfying the following conditions.

  • $U_i$ represents the hand you play in round $100+i$.
  • For all $1\leq i\leq N$, $U_i$ beats the hand Alice plays in round $100+i$.

It can be proved that, under the constraints of this problem, different initial states never generate the same string $T$.

Input

The input is given from standard input in the following format.

$T$
$N$
  • $T$ is a string of length $100$
  • Each character of $T$ is one of R, S, P, X
  • $T$ is generated by the pseudocode in the problem statement
  • $1\leq N\leq 2\times10^5$
  • $N$ is an integer

Output

Output the answer on $1$ line. End the output with a newline.

Sample

Sample 1
Input
SSSXSRPPSRXXPPSSRRSSXSXXPSSRXPXRSRRRPPPXSPXXXSSRSSXXRSRRRRXSSPRXRRRPSRPSRRRSPSXRSRPRRRXXSXRSXSRPXSRX
1
Output
X
Sample 2
Input
XXXPSRRXPXXRRRPSXPRRRPSSRSXRSPSPXPPSSRRRXPSXSRRXRXSPXXRPPSSPSRPPPXSRSPRPSRXRSSPSRPSRPPRSPRSRSSXXPPXS
5
Output
PXSPR

Sample 3
Input
SXRRRSSSXSRRRSPSPSSRXPRSPSRSRXPRXSRXRPPPPPSSSRPSSRSRSXRRPPXRRSRXXSRSXXXXRPPRRSPSRSRXXSRPPXSRPSPPSRPR
10
Output
RPSRXPPSXP

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。