CF838F Expected Earnings

你正在玩一个有红球和黑球的游戏。一开始，你被告知袋子中共有 $n$ 个球。此外，你还知道袋子中恰好有 $i$ 个红球的概率为 $p_{i}/10^{6}$。 你现在想从这个袋子中买球。你非常喜欢红色，因此红球的价值为 $1$ 单位，而黑球没有价值。每次买球时，如果袋子中还有球，你需要支付 $c$ 的费用（$0 \leq c \leq 1$），然后随机从袋子中抽取一个球。你可以在任何时刻选择停止购买（你甚至可以选择什么都不买）。 如果你总是以最大化期望利润（即红球数量减去获得红球所需的花费）的方式购买，请输出最大的期望利润。

输入的第一行包含两个整数 $n, X$（$1 \leq n \leq 10000$，$0 \leq X \leq 10^6$）。 第二行包含 $n+1$ 个整数 $p_{0}, p_{1}, \ldots, p_{n}$（$0 \leq p_{i} \leq 10^{6}$，并且 $p_0 + p_1 + \cdots + p_n = 10^6$）。 $c$ 的值可以按如下公式计算： $$ c = \frac{X}{10^6} $$

输出一个浮点数，表示最大期望值。 如果你的答案和标准答案的绝对误差或相对误差不超过 $10^{-9}$ 即视为正确。更具体地说，设你的答案为 $a$，标准答案为 $b$，只要满足 $$ \frac{|a-b|}{\max(1, |b|)} \leq 10^{-9} $$ 你的答案即为正确。

在本样例中，袋子中恰好有 0、1、2、3 个红球的概率相等。同时，每次抽球的花费为 $0.2$。 由 ChatGPT 5 翻译