← 返回题目列表

Codeforces · 167/B

B. 奇才和巨额奖金

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

要想在巫术比赛中取得好成绩,必须进行大量训练。所以,有无数的魔法学校和魔法费用。

其中一所魔法学校由n个游览组成。每次巡回赛的获胜者都会获得巨额奖金。学校组织得比较远,得把所有奖品一次性带回家。您随身携带的袋子最多可容纳 k 个巨额奖品。

除了想把所有奖品带回家之外,你还想表现出色。如果你赢得至少 l 场比赛,你就会认为你的表现很好。

事实上,多年的比赛组织经验向组织者证明,运送巨额奖品对于参赛者来说是一个问题。唉,没有人发明过一种可以减少奖金的咒语……所以,解决方案是这样的:对于某些巡回赛,获胜者会得到一个袋子,而不是巨额奖金。每个袋子都有一个数字 ai,即可以放入其中的巨额奖品的数量。

你已经知道所有旅行的主题,因此你可以估计赢得第 i 次旅行的概率 pi。在任何情况下您都不能跳过此行程。

计算您在比赛中表现出色并能够将所有赢得的奖品带回家的概率(也就是说,您将能够将赢得的所有巨额奖品装入您赢得的或从家里带来的袋子中)。

输入

第一行包含三个整数 n、l、k (1 ≤ n ≤ 200, 0 ≤ l, k ≤ 200) — 相应的旅游次数、赢得的最少旅游次数以及您从家里带来的包里可以装的奖品数量。

第二行包含 n 个空格分隔的整数 pi (0 ≤ pi ≤ 100) — 赢得第 i 场比赛的概率,以百分比为单位。

第三行包含 n 个空格分隔的整数,ai (1 ≤ ai ≤ 200) — 赢得第 i 次巡回赛时奖励给您的袋子的容量,如果第 i 次巡回赛的奖品是巨奖而不是袋子,则为 -1。

输出

打印一个实数——问题的答案。如果绝对误差或相对误差不超过 10 - 6,答案将被接受。

示例

输入 #1

3 1 0
10 20 30
-1 -1 2

输出 #1

0.300000000000

输入 #2

1 1 1
100
123

输出 #2

1.000000000000

注意

在第一个示例中,我们需要赢得任何巡回赛或赢得第三场巡回赛。如果我们什么也没赢得,我们就不会表现得很好。所以,我们必须赢得第三次巡回赛。在这种情况下将满足其他条件。赢得第三次巡回赛的概率是0.3。

在第二个样本中,我们以 1.0 的概率赢得了唯一一场巡回赛,然后带着包回家了。