CF1267G 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$。 由 ChatGPT 4.1 翻译