P14815 [ICPC 2023 Yokohama R] Rank Promotion
题目描述
Quiz Solver 是一款流行的在线电脑游戏。每次玩家打开游戏的移动应用程序，都会显示一个新的测验。玩家提交测验的答案，然后会被判断为正确或错误，结果会累积到数据库中。当玩家在多个测验中表现出高准确率时，玩家在游戏中的 **等级** 就会提升。
玩家等级是非负整数，每个玩家以等级 0 开始游戏。当玩家在足够长的测验序列中达到较高的正确率时，玩家将被提升到下一个等级。更精确地说，等级提升系统由两个参数定义：一个整数 $c$ 和一个有理数 $p/q$。在第 $e$ 个测验结束后，如果存在一个整数 $s$ 满足以下条件，玩家的等级会立即增加一：
- $1 \le s \le e - c + 1$。
- 玩家在第 $s$ 个测验开始之前已经处于当前等级。
- 从第 $s$ 个到第 $e$ 个测验的正确率高于或等于 $p/q$。
否则，等级保持不变。
有一天，Quiz Solver 的管理员发现由于数据库故障，玩家的等级数据丢失了。幸运的是，测验解答记录日志完全无损地保存了下来。你的任务是根据玩家的解答记录重新计算每个玩家的等级。
输入格式
输入由单个测试用例组成，格式如下。
$$
\begin{aligned}
&n\ c\ p\ q \\
&S_1 \cdots S_n
\end{aligned}
$$
第一行包含四个整数，满足以下约束：$1 \le n \le 5 \times 10^5$，$1 \le c \le 200$，以及 $1 \le p \le q \le 5 \times 10^5$。第一个整数 $n$ 是一个玩家解答的测验数量。参数 $c$、$p$ 和 $q$ 的含义在题目描述中说明。
$S_1 \cdots S_n$ 是一个字符串，描述了玩家的测验解答记录。每个 $S_i$ 要么是 Y，表示玩家对第 $i$ 个测验的答案正确；要么是 N，表示错误。
输出格式
在一行中输出玩家在第 $n$ 个测验结束后的最终等级。
说明/提示
在样例输入 1 中，玩家在完成第四个测验后晋升到等级 1，因为正确率 $3/4$ 高于 $p/q = 4/7$。注意，在第三个测验时没有晋升，因为只回答了三个测验，少于 $c = 4$。然后，在第十一个测验后，玩家晋升到等级 2。
:::align{center}
图 B.1. 样例输入 1 的等级晋升时间点
:::