AT_xmascon22_b.Battle Solving

给定整数 $N, K, P$，以及由字符 A、B 组成的长度为 $N$ 的字符串 $S$。对于每个 $k=1,2,\ldots,K$，请分别回答下面的问题（每个 $k$ 独立考虑）。

くろうさ和しろうさ进行一道题一道题的抢答竞赛。第 $i$ 道题（$i=1,2,\ldots$）的规则如下：

• 若 $i\le N$ 且 $S$ 的第 $i$ 个字符为 A，则くろうさ先答对的概率为 $\frac{P}{100}$，しろうさ先答对的概率为 $1-\frac{P}{100}$。
• 若 $i\le N$ 且 $S$ 的第 $i$ 个字符为 B，则くろうさ先答对的概率为 $1-\frac{P}{100}$，しろうさ先答对的概率为 $\frac{P}{100}$。
• 若 $i > N$，则くろうさ和しろうさ先答对的概率都是 $\frac{1}{2}$。

“第 $i$ 道题由くろうさ先答对”这一事件间彼此独立。

只要有任意一只兔子先答对 $k$ 道题，比赛即结束，该兔子即为优胜者。请比较くろうさ成为优胜者的概率与 $\frac{1}{2}$ 的大小关系。

输入为标准输入，格式如下：

$N$ $K$ $P$ $S$

请输出一个长度为 $K$ 的字符串，对于每个 $k=1,2,\ldots,K$：

• 若くろうさ成为优胜者的概率大于 $\frac{1}{2}$，第 $k$ 个字符输出 +。
• 若概率等于 $\frac{1}{2}$，第 $k$ 个字符输出 0。
• 若概率小于 $\frac{1}{2}$，第 $k$ 个字符输出 -。

样例解释 1

当 $k=1$ 时，くろうさ先答对第 1 题的概率为 $\frac{1}{4}$，因此くろうさ获胜的概率为 $\frac{1}{4}$。

当 $k=2$ 时：

• くろうさ先答对第 1 题，且第 2 题也由くろうさ先答对的概率为 $\frac{3}{16}$；
• くろうさ先答对第 1 题，第 2 题由しろうさ先答对，第 3 题由くろうさ先答对的概率为 $\frac{1}{32}$；
• しろうさ先答对第 1 题，第 2 题由くろうさ先答对，第 3 题也由くろうさ先答对的概率为 $\frac{9}{32}$；

因此くろうさ优胜的概率为 $\frac{1}{2}$。

数据范围

• $1 \le N \le 10^5$。
• $1 \le K \le 10^5$。
• $0 \le P \le 100$。
• $S$ 是由 A 和 B 组成的长度为 $N$ 的字符串。

由 ChatGPT 5 翻译