配点 : 100 点
编程竞赛的题目大多可以分为计数和优化两大类。兔子们似乎也有擅长和不擅长的题目类型。
問題文
整数 N, K, P 以及,给定字符 A, B 组成的长度 N 的字符串 S 。对于每个 k = 1, 2, \ldots, K 回答以下问题(每个 k 的问题须分别考虑)。
黑兔和白兔进行题目快速解答竞赛。题目每次出 1 道,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} 黑兔先解出,概率 \frac{1}{2} 白兔先解出。
「i 第 x 道题被黑兔先解出”这些事件是相互独立的。
“先解出的题目” k 当到达问题的兔子出现时,比赛结束,该兔子获胜。比较黑兔获胜的概率与 \frac{1}{2} 可以得到第大小。
制約
- 1 \le N \le 10^5.
- 1 \le K \le 10^5.
- 0 \le P \le 100.
- S 是
您也可以写
A,B组成的长度 N 的字符串。
入力
输入是按以下格式从标准输入给出的。
N K P S
出力
输出如下长度 K 的字符串:每个 k = 1, 2, \ldots, K , 定义
- 如果黑兔获胜的概率大于 \frac{1}{2} 如果更大,k 第一个字符是
+是。 - 如果黑兔获胜的概率大于 \frac{1}{2} 等于k 第一个字符是
0是。 - 如果黑兔获胜的概率大于 \frac{1}{2} 小于k 第一个字符是
-是。
入力例 1
2 2 25 AB
出力例 1
-0
k = 1 时,1 第x题黑兔先解的概率为 \frac{1}{4} ,所以黑兔获胜的概率是 \frac{1}{4} 是。
k = 2 时,
- 1 第x题黑兔先解,2 第x题黑兔先解的概率为 \frac{3}{16}
- 1 第x题黑兔先解,2 第x题白兔先解,3 第x题黑兔先解的概率为 \frac{1}{32}
- 1 第x题白兔先解,2 第x题黑兔先解,3 第x题黑兔先解的概率为 \frac{9}{32}
,所以黑兔获胜的概率是 \frac{1}{2} 是。
入力例 2
10 4 99 AABBBAABBB
出力例 2
++-+