596D · Wilbur and Trees

Problem: Wilbur the pig really wants to be a beaver, so he decided today to pretend he is a beaver and bite at trees to cut them down.

There are n trees located at various positions on a line. Tree i is located at position xi. All the given positions of the trees are distinct.

The trees are equal, i.e. each tree has height h. Due to the wind, when a tree is cut down, it either falls left with probability p, or falls right with probability 1 - p. If a tree hits another tree while falling, that tree will fall in the same direction as the tree that hit it. A tree can hit another tree only if the distance between them is strictly less than h.

For example, imagine there are 4 trees located at positions 1, 3, 5 and 8, while h = 3 and the tree at position 1 falls right. It hits the tree at position 3 and it starts to fall too. In it's turn it hits the tree at position 5 and it also starts to fall. The distance between 8 and 5 is exactly 3, so the tree at position 8 will not fall.

As long as there are still trees standing, Wilbur will select either the leftmost standing tree with probability 0.5 or the rightmost standing tree with probability 0.5. Selected tree is then cut down. If there is only one tree remaining, Wilbur always selects it. As the ground is covered with grass, Wilbur wants to know the expected total length of the ground covered with fallen trees after he cuts them all down because he is concerned about his grass-eating cow friends. Please help Wilbur.

Input Format: The first line of the input contains two integers, n (1 ≤ n ≤ 2000) and h (1 ≤ h ≤ 108) and a real number p (0 ≤ p ≤ 1), given with no more than six decimal places.

The second line of the input contains n integers, x1, x2, ..., xn ( - 108 ≤ xi ≤ 108) in no particular order.

Output Format: Print a single real number — the expected total length of the ground covered by trees when they have all fallen down. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$.

Note: Consider the first example, we have 2 trees with height 2.

1. Both trees falls left. This can either happen with the right tree falling left first, which has $\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$ probability (also knocking down the left tree), or the left tree can fall left and then the right tree can fall left, which has $\frac{1}{4} \cdot \frac{1}{2} = \frac{1}{8}$ probability. Total probability is $\frac{1}{4} + \frac{1}{8} = \frac{3}{8}$.

2. Both trees fall right. This is analogous to (1), so the probability of this happening is $\frac{3}{8}$.

3. The left tree fall left and the right tree falls right. This is the only remaining scenario so it must have $1 - \frac{3}{8} - \frac{3}{8} = \frac{1}{4}$ probability.

Cases 1 and 2 lead to a total of 3 units of ground covered, while case 3 leads to a total of 4 units of ground covered. Thus, the expected value is $3 \cdot (\frac{3}{8}) + 3 \cdot (\frac{3}{8}) + 4 \cdot (\frac{1}{4}) = 3.25$.