P16847 [GKS 2021 #C] Rock Paper Scissors

你和你的朋友喜欢玩石头剪刀布。每天你们恰好玩 $60$ 轮，并在每天结束时统计这 $60$ 轮的得分。 在每一轮中，你们各自在不知道对方选择的情况下做出选择。然后，你们同时亮出选择并计算得分。石头赢剪刀，剪刀赢布，布赢石头。用 $\texttt{R}$、$\texttt{P}$、$\texttt{S}$ 分别表示石头、布和剪刀。每天你们都会商定两个值 $W$ 和 $E$。如果你的选择获胜，你会得到 $W$ 分。如果你和你的朋友选择相同，你会得到 $E$ 分。如果你的选择落败，你则得不到分。 某天，你无意中看到了朋友写在一个笔记本上的策略。你的朋友会记录当天到目前为止你选择 $\texttt{R}$、$\texttt{P}$、$\texttt{S}$ 的次数。设 $A_i$ 是你在第 $i$ 轮的选择（$\texttt{R}$、$\texttt{P}$ 或 $\texttt{S}$），$B_i$ 是朋友在同一轮的选择。令 $r_i$ 为对于 $1 \le j \le (i-1)$ 满足 $A_j = \texttt{R}$ 的次数。类似地，$p_i$ 和 $s_i$ 分别是在第 $i$ 轮之前你选择 $\texttt{P}$ 和 $\texttt{S}$ 的总次数。 在每天的第 $1$ 轮，$i=1$ 且 $r_1=s_1=p_1=0$，由于缺乏信息，你的朋友会随机选择（即你的朋友以 $\frac{1}{3}$ 的概率选择每一种选项）。在之后的每一轮，你的朋友根据以下方式决定 $B_i$：以概率 $\Pr[\texttt{R}] = \frac{s_i}{i-1}$ 选择 $\texttt{R}$，以概率 $\Pr[\texttt{P}] = \frac{r_i}{i-1}$ 选择 $\texttt{P}$，以概率 $\Pr[\texttt{S}] = \frac{p_i}{i-1}$ 选择 $\texttt{S}$。这个策略是自适应且难以击败的！ 你即将去度假 $T$ 天。你需要给助理留下指令，告诉他每天每一轮应该选择什么。设整数 $X$ 是你期望在这 $T$ 天游戏后获得的平均奖励。给定 $W$ 和 $E$（每天的值可能不同），请提供你的指令，形式为一个长度为 $60$ 的字符串，从第 $1$ 轮到第 $60$ 轮。每个字符表示你在对应轮的选择。你的目标是选择你的指令集，使得在所有游戏天数中，你获得的奖励的期望平均值至少为 $X$。注意，你可以针对不同的 $W$ 和 $E$ 选择不同的指令。

输入的第一行给出天数 $T$。第二行包含一个整数 $X$，即你在这些天之后的目标平均奖励。然后是对 $T$ 天的描述。每天由两个整数 $W$ 和 $E$ 描述。$W$ 是当天每轮你获胜时得到的分数，$E$ 是当天每轮你与朋友选择相同时得到的分数。 所有测试（除下面的样例测试外）按如下方式生成。我们选择 $50$ 个介于 $5$ 到 $95$ 之间的不同值 $G$（均匀分布）。然后，对于这些值中的每一个，会有 $4$ 天，其中 $W = 10 \times G$，而 $E$ 分别等于 $W$、$\frac{W}{2}$、$\frac{W}{10}$ 和 $0$。不要对这些天的顺序做任何假设。

对于每一天，输出一行，格式为 `Case #x: A1A2...A60`，其中 $x$ 是当天编号（从 $1$ 开始），$A_i$ 是你在当天第 $i$ 轮游戏中选择的 $\texttt{R}$、$\texttt{P}$ 或 $\texttt{S}$。选择之间不应有空格。 这些选择应使得在 $T$ 天后，期望值的平均值大于或等于 $X$。对于每个测试用例，可能存在多种解，你可以输出其中任意一种。保证对于给定的 $X$，存在一个解。

在这个样例测试中，我们所有 $T = 2$ 天的目标（平均）奖励为 $30$。 对于第一天，由于 $W = 60$，你可以通过至少获胜一次来达到总目标。一种可能的策略是只争取那一次胜利。 - 在第 $1$ 轮，你选择 $A_1 = \texttt{R}$。你获胜、平局或落败的概率相等，因此期望值为 $20$。 - 在第 $2$ 轮，$r_2 = 1$，$p_2 = s_2 = 0$。你的朋友选择 $\texttt{P}$ 的概率为 $\Pr[\texttt{P}] = r_2 / 1 = 1$，这保证了你的朋友的选择 $B_2 = \texttt{P}$。 - 如果你选择 $A_2 = \texttt{S}$，则保证获胜，在第 $2$ 轮获得 $60$ 分。 - 无论你在接下来的所有轮中选择什么，仅两轮之后的期望值就已经是 $20 + 60 = 80$，足以达到我们的目标。 此外，由于我们在所有 $2$ 天中的平均值已经至少为 $\frac{80}{2} = 40 \ge X = 30$，第二天我们可以使用任何策略。 注意，这并不是唯一的解。只要平均期望得分 $\ge 30$，其他输出也会被接受。 ### 限制条件 $T = 200$（除样例中 $T = 2$ 外）。 $50 \le W \le 950$。 $0 \le E \le W$，且 $E$ 是 $W$、$\frac{W}{2}$、$\frac{W}{10}$ 或 $0$ 之一。 每天恰好玩 $60$ 轮。 **测试集 1** $X = 14600$。 **测试集 2** $X = 15500$。 **测试集 3** $X = 16400$。 翻译由 DeepSeek V4 Pro 完成