P12940 [NERC 2019] Game Relics

电子竞技是一种使用电子游戏进行的竞技运动。Dota 2 是电子竞技中最受欢迎的竞技游戏之一。最近，一款新游戏 Dota 3 发布了。在 Dota 3 中，玩家可以为自己的英雄购买一些**圣物**。圣物是用于追踪英雄在游戏中行为和统计数据的计数器。 Gloria 喜欢玩 Dota 3，因此她想为她最喜欢的英雄购买所有 $n$ 件可用的圣物。 圣物可以使用游戏内货币"碎片"购买。每件圣物都有自己的价格——第 $i$ 件圣物需要 $c_i$ 碎片。玩家可以通过以下两种方式购买圣物： - 支付 $c_i$ 碎片直接购买第 $i$ 件圣物； - 支付 $x$ 碎片随机获得所有 $n$ 件圣物中的一件。每件圣物被获得的概率相同。如果获得重复的圣物，则该圣物会被回收，并返还 $\frac{x}{2}$ 碎片给玩家。 Gloria 想要购买所有 $n$ 件圣物。请帮助她最小化购买所有圣物所需的期望碎片数量。

第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 100$；$1 \le x \le 10\,000$）——圣物的数量和随机获取一件圣物的花费。 第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$x \le c_i \le 10\,000$；$\sum{c_i} \le 10\,000$）——$n$ 件圣物的价格。

输出一个实数——Gloria 购买所有圣物所需的最小期望碎片数量。 绝对误差或相对误差不应超过 $10^{-9}$。

在第一个示例中，最优策略是先花费 $20$ 碎片随机获取两件圣物中的一件。之后会出现两种情况： 第一种情况是 Gloria 获得了第一件圣物。然后她需要继续随机获取圣物，直到获得第二件圣物。这种情况下的期望花费是 $20 + 30 = 50$ 碎片。 第二种情况是 Gloria 一开始就获得了第二件圣物。这时最好直接花费 $25$ 碎片购买第一件圣物，因此这种情况下的期望花费是 $20 + 25 = 45$ 碎片。 因此，总的期望花费为 $\frac{50 + 45}{2} = 47.5$ 碎片。 翻译由 DeepSeek V3 完成