← 返回题目列表

AtCoder · xmascon22_b

B. 战斗解决

中文机器翻译题面 查看原题

配点 : 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

++-+