410350: GYM104011 J Journey in Fog

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Journey in Fogtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Julia and Jane are two friends living at the opposite ends of a long narrow street of length $$$L$$$.

Today, Julia needs to meet Jane and return home as soon as possible.

Jane has a list of speeds $$$v_1, v_2, \ldots, v_n$$$. At time $$$0$$$, Jane picks an integer $$$i$$$ from $$$1$$$ to $$$n$$$ uniformly at random, and starts moving towards Julia at a constant speed of $$$v_i$$$.

Julia is not as restricted in her movements, though. Starting from time $$$0$$$, Julia can freely move along the street in any direction at any speed not exceeding $$$V$$$. In particular, Julia can stay at the same place as long as she wants, move at speeds lower than $$$V$$$, and change her speed at any moment.

It's foggy outside. Hence, Julia and Jane can not see each other unless they are at the same point of the street. Also note that Julia does not know Jane's speed, but she knows the list $$$v_1, v_2, \ldots, v_n$$$.

Suppose Julia meets Jane and arrives back home at time $$$t$$$. Julia will follow a strategy that minimizes the expected value of $$$t$$$. Find that expected value.

Input

The first line contains three integers $$$n$$$, $$$L$$$, and $$$V$$$ — the number of speeds on Jane's list, the length of the street, and Julia's maximum speed ($$$1 \le n \le 10^5$$$; $$$1 \le L \le 10^9$$$; $$$1 \le V \le 10^6$$$).

The second line contains $$$n$$$ integers $$$v_1, v_2, \ldots, v_n$$$ — the list of possible speeds of Jane in ascending order ($$$1 \le v_1 < v_2 < \dotsb < v_n \le 10^6$$$).

Output

Print a single real number — the expected amount of time it will take Julia to meet Jane and return back home, if she follows an optimal strategy. Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-9}$$$.

ExamplesInput
1 1000 30
10
Output
50.0000000000000
Input
1 1000 10
30
Output
33.3333333333333
Input
4 1000 20
10 20 30 40
Output
46.2500000000000
Note

In the first example test, Julia is much faster than Jane. It's best for Julia to move towards Jane as fast as she can, meet her at time $$$25$$$ at distance $$$750$$$ away from home, and return back home at time $$$50$$$.

In the second example test, Jane is much faster than Julia. It's best for Julia to just wait for Jane at home, where Jane will arrive at time $$$\frac{1000}{30}$$$.

加入题单

上一题 下一题 算法标签: