← 返回题目列表

AtCoder · utpc2021_m

M. 开门

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

配点 : 100 点

問題文

你面前有一扇锁着的门。锁匠 您有 N 键,其中只有一个是正确的。 第 i 个密钥是正确密钥的概率为 p_i %。

门的结构很差,即使您选择了正确的钥匙也不一定能打开。 如果您尝试使用第 i 把钥匙开门,门打开的概率如下。 如果第

  • i 个键是正确的键: q_i 门打开的几率为 %。如果您多次尝试打开它,它将被独立判断。 如果第
  • i 钥匙不是正确的钥匙:门将无法打开。

你是第一个 K 我有日元。 门会打开,否则你的钱就会被 0 执行以下操作,直到得到一个圆圈。

  • 给锁匠 1 支付日元。从锁匠那里选择一把钥匙,借用它,并尝试打开一次门。 然后归还钥匙。
您的目标是在操作结束时最大化剩余资金的预期价值。 找到以最佳方式操作时的最大期望值。

制約

  • 所有输入均为整数 如果有办法做到
  • 1 \le N,K \le 100
  • 1 \le p_i ,q_i \le 100
  • p_i 的总和是 在 100

入力

输入是按以下格式从标准输入给出的。

N K
p_1 \ldots p_N
q_1 \ldots q_N

出力

答案 将除以 1 行输出。绝对误差或相对误差 10^{-6} 如果答案如下,则判定为正确。


入力例 1

2 2
50 50
50 50

出力例 1

0.25

手里有钱 1 如果你还剩下日元以上并且门没有打开, 考虑选择第 1 个 key 的策略。概率 25 % 1 剩余日元,概率 75 % 0 是日元。余额的预期值为 0.25 这实际上是最大期望值。 只需选择第


入力例 2

1 2
100
100

出力例 2

1

1 个键即可。 考虑


入力例 3

10 20
10 10 10 20 6 5 4 8 12 15
10 20 30 40 50 60 70 80 90 10

出力例 3

8.2045400000000000031