您正在玩一袋红球和黑球的游戏。最初,您被告知袋子共有 n 个球。此外,您还被告知该袋子有恰好包含 i 个红球的概率 pi / 106。
您现在想从这个袋子里购买球。你真的很喜欢红色,所以红球的价值为 1,而黑球则一文不值。购买球时,如果袋子里还有球,则支付成本 c(0 ≤ c ≤ 1),然后从袋子中随机抽取一个球。您可以选择随时停止购买(甚至可以选择根本不购买任何东西)。
鉴于您以最佳方式购买以使预期利润最大化(即 # 个红球 - 获得它们所需的成本),请打印最大预期利润。
输入
输入的第一行将包含两个整数 n, X (1 ≤ n ≤ 10 000, 0 ≤ X ≤ 106)。
输入的下一行将包含 n + 1 个整数 p0, p1, ... pn (0 ≤ pi ≤ 106, $$\sum_{i=0}^{n} p_i = 10^6$$)
c 的值可以计算为 $$\frac{x}{10^6}$$。
输出
打印代表最佳期望值的单个浮点数。
如果您的答案的绝对或相对误差最多为 10 - 9,则您的答案将被接受。更具体地说,如果您的答案是 a 而陪审团的答案是 b,则您的答案将被接受,如果 $${ \frac { | } a - b | } { \operatorname* { m a x } ( 1, b ) } } \leq 1 0 ^ { - 9 }$$。
示例
输入 #1
3 200000 250000 250000 250000 250000
输出 #1
0.9000000000
注意
此处,袋子中包含 0,1,2,3 个红球的概率相等。另外,从袋子里取出一个球需要花费 0.2 美元。