CF2181J Jinx or Jackpot

杰克正待在他最喜欢的赌场，手头有 $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$，如下面所述。 在老虎机上，杰克可以下注 $x$ 美元，其中 $x$ 是非负整数，然后拉动拉杆。接下来： 1. 以概率 $\frac{p_i}{100}$，出现大奖，老虎机返还 $2x$ 美元，即他净赚 $x$ 美元。 2. 以概率 $1 - \frac{p_i}{100}$，出现厄运，老虎机不会返还钱，即他亏损 $x$ 美元。 即便杰克下注 $0$ 美元，拉杆后也会知道这次是大奖还是厄运。 此外，老虎机并不坚固，最多只能拉 $k$ 次。 请你求出杰克通过最优策略能获得的最大期望收益。收益定义为最终拥有的钱减去初始的 $1000$ 美元。 显然，杰克不能下注比他当前余额还多的钱。

第一行包含两个整数 $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}$，则视为正确。

由 ChatGPT 5 翻译