← 返回题目列表

Codeforces · 1874/D

D. 水母和 Miku

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

有 $$$n + 1$$$ 个城市,编号从 $$$0$$$ 到 $$$n$$$,由 $$$n$$$ 道路连接。第 $$$i$$$-th $$$(1 \leq i \leq n)$$$ 路双向连接城市 $$$i-1$$$ 和城市 $$$i$$$。当水母飞回城市$$$0$$$后,她发现她把Miku fufu落在了城市$$$n$$$。

每条路都有一个正整数的美丽程度。将第$$$i$$$条路的美丽表示为$$$a_i$$$。

水母正在寻找她的福福。由于方向感很差,她不知道该走哪条路。每天,她都会随机选择一条与她当前所在城市相连的道路并穿过它。令 $$$s$$$ 为连接当前城市的道路美景的总和。对于每条连接当前城市的道路,Jellyfish 都会以 $$$\frac x s$$$ 的概率遍历该道路,其中 $$$x$$$ 是道路的美景,到达道路另一边的城市。

Jellyfish将从城市$$$0$$$开始,当她到达城市$$$n$$$时,她只会得到她的fufu。

您想要选择美丽的道路,以使水母找到她的福福所需的预计天数尽可能短。但由于资金有限,所有道路的美女总和必须小于或等于$$$m$$$。

如果选择了最佳的道路美景,求水母恢复她的福福所需的最少预计天数。

输入

输入的第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq m \leq 3000$$$) - 道路的数量和道路美丽的最大总和。

输出

输出如果道路的美丽被最佳选择,水母需要得到她的福福的最少预期天数。

如果绝对或相对误差不超过 $$$10^{-9}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$$$,则认为您的答案是正确的。

示例

输入 #1

3 8

输出 #1

5.200000000000

输入 #2

10 98

输出 #2

37.721155173329

注意

在第一个例子中,美丽的最优分配是$$$a=[1, 2, 5]$$$。水母取回她的福福所需的预计天数是 $$$5.2$$$。