Codeforces Round 901 (Div. 1)
D
Jellyfish and Miku
Codeforces
2800
原题
← CE →
翻译中…

There are $n + 1$ cities with numbers from $0$ to $n$, connected by $n$ roads. The $i$-th $(1 \leq i \leq n)$ road connects city $i-1$ and city $i$ bi-directionally. After Jellyfish flew back to city $0$, she found out that she had left her Miku fufu in city $n$.

翻译中…

Each road has a positive integer level of beauty. Denote the beauty of the $i$-th road as $a_i$.

翻译中…

Jellyfish is trying to find her fufu. Because of her poor sense of direction, she doesn't know which way to go. Every day, she randomly chooses a road connected to the city she currently is in and traverses it. Let $s$ be the sum of the beauty of the roads connected to the current city. For each road connected to the current city, Jellyfish will traverse the road with a probability of $\frac x s$, where $x$ is the beauty of the road, reaching the city on the other side of the road.

翻译中…

Jellyfish will start at city $0$, and she will get only her fufu back when she reaches city $n$.

翻译中…

You want to choose the beauty of the roads such that the expected number of days Jellyfish takes to find her fufu will be the minimum possible. However, due to limited funding, the sum of beauties of all roads must be less than or equal to $m$.

翻译中…

Find the minimum expected number of days Jellyfish needs to get her fufu back if the beauty of the roads is chosen optimally.

翻译中…

Input

翻译中…

The first and only line of the input contains two integers $n$ and $m$ ($1 \leq n \leq m \leq 3000$) — the number of the roads and the maximum sum of beauty of the roads.

翻译中…

Output

翻译中…

Output the minimum expected number of days Jellyfish needs to get her fufu back if the beauty of the roads is chosen optimally.

翻译中…

Your answer will be accepted if the absolute or relative error does not exceed $10^{-9}$. Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$.

翻译中…

Note

翻译中…

In the first example, the optimal assignment of beauty is $a=[1, 2, 5]$. The expected number of days Jellyfish needs to get her fufu back is $5.2$.

翻译中…

样例

Input #1
3 8
Output #1
5.200000000000
InputCopy OutputCopy
Input #2
10 98
Output #2
37.721155173329
InputCopy OutputCopy
题目信息
题号
1874D
时间限制
2 s
内存限制
512 MB
标签
分治
动态规划
数学
概率论

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。