← 返回题目列表

Codeforces · 1267/G

G. 游戏文物

中文机器翻译题面 查看原题

电子竞技是一种使用视频游戏的竞技运动形式。 Dota 2 是电子竞技领域最受欢迎的竞技视频游戏之一。最近,一款新的视频游戏 Dota 3 发布了。在 Dota 3 中,玩家可以为他们的英雄购买一些圣物。遗物是追踪英雄在游戏中的行动和统计数据的计数器。

Gloria 喜欢玩 Dota 3,因此她想为她最喜欢的英雄购买所有可用的 $$$n$$$ 遗物。

可以使用称为碎片的游戏内货币购买遗物。每个圣物都有自己的价格——第 $$$i$$$ 个圣物的 $$$c_i$$$ 碎片。玩家可以使用以下选项之一购买圣物:

- 支付 $$$c_i$$$ 碎片购买第 $$$i$$$ 遗物;
- 支付 $$$x$$$ 碎片并随机获得所有 $$$n$$$ 遗物之一。所有 $$$n$$$ 遗物获得遗物的概率是相同的。如果收到重复的遗物,则该遗物将被回收,并将 $$$\frac{x}{2}$$$ 碎片返还给玩家。

格洛丽亚想要购买所有 $$$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$$$ 文物的价格。

输出

打印一个实数——格洛丽亚购买所有圣物所需花费的最小预期碎片数量。

绝对或相对误差不应超过 $$$10^{-9}$$$。

示例

输入 #1

2 20
25 100

输出 #1

47.50000000000000000

输入 #2

4 30
60 50 60 80

输出 #2

171.25000000000000000

注意

在第一个示例中,最佳策略是随机获取支付 $$$20$$$ 碎片的两个文物之一。那么有两种情况。

如果格洛丽亚收到第一个圣物,就会发生第一个事件。然后她不断获得随机圣物,直到获得第二个圣物。在这种情况下预计花费的分片数量为 $$$20 + 30 = 50$$$。

在第二个场景中,格洛丽亚最初获得第二件圣物。那么最好用 $$$25$$$ 碎片购买第一个圣物,因此在这种情况下预计花费的碎片数量为 $$$20 + 25 = 45$$$。

因此,预计花费的分片数量为 $$$\frac{50 + 45}{2} = 47.5$$$。