杰克在他最喜欢的赌场里,有 $$$1000$$$ 美元。赌场实际上只有一台老虎机。杰克知道这个赌场的历史。曾几何时,未来的赌场老板正在散步,突然看到一数组 $$$n$$$ 整数 选择 $$$p_{1}、\dots、p_{n}$$$ 各从 $$$0$$$ 到 $$$100$$$。他均匀地随机选择一个索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并认为创建一个赌场是个好主意,其中只有一台老虎机,头奖概率为 $$$\frac{p_i}{100}$$$。他创造了它。
杰克知道主人在散步时突然出现的一系列选择 $$$p_{1}, \dots, p_{n}$$$,但他不知道主人选择了哪个 $$$i$$$。然而,所选择的索引 $$$i$$$ 是永远固定的;老虎机始终使用相同的 $$$p_i$$$,如下所述。
在老虎机上,Jack 可以下注 $$$x$$$ 美元,其中 $$$x$$$ 是 非负 整数,然后拉动控制杆。然后:
- 有概率 $$$\frac{p_i}{100}$$$ 中奖,老虎机向他返还 $$$2x$$$ 美元,因此他获得 $$$x$$$ 美元。
- 概率为 $$$1 - \frac{p_i}{100}$$$ 这将是一个恶咒,老虎机不会向他返回任何内容,因此他会损失 $$$x$$$ 美元。
即使杰克下注 $$$0$$$ 美元,他也会明白这是恶咒还是大奖。
另外,老虎机不是很耐用,所以杰克最多可以在上面玩 $$$k$$$ 轮。
求最大期望值 利润 杰克可以通过最优策略来实现。这里利润被定义为杰克的最终金额减去他最初的 $$$1000$$$ 美元。
当然,Jack 的赌注不能超过他当前的余额。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 100\,000$$$; $$$1 \leq k \leq 30$$$) — 选择数和轮数限制。第二行包含 $$$n$$$ 整数 $$$p_{1}, \dots, p_{n}$$$ ($$$0 \le p_i \le 100$$$) — 选项。
输出
输出一个实数——杰克通过最优策略可以获得的预期利润。如果您的答案的绝对或相对误差最多为 $$$10^{-4}$$$,则您的答案将被视为正确。
示例
输入复制
2 270 30
输出复制
160
输入复制
2 3030 70
输出复制
12099716.1778528057038784
输入复制
2 540 50
输出复制
0
输入复制
6 610 20 60 30 40 50
输出复制
29.40799999999990177457221
输入复制
1 561
输出复制
1702.708163199999489734182