Wilbur and Trees

题意翻译

有$n$课树并排排列，每棵树高$h$。每次从剩余的树中选最左边的或最右边的（概率相等为0.5），砍掉一棵树，树倒向左边的概率为$p$，倒向右边的概率为$1-p$。如果树和相邻树的距离小于$h$，树倒时会把相邻的树撞倒，倒的方向和撞到它的树一致。问，砍完所有树，树干覆盖的草地长度的期望值。

题目描述

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 $ x_{i} $ . 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.

输入输出格式

输入格式

The first line of the input contains two integers, $ n $ $ (1<=n<=2000) $ and $ h $ $ (1<=h<=10^{8}) $ 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, $ x_{1},x_{2},...,x_{n} $ $ (-10^{8}<=x_{i}<=10^{8}) $ in no particular order.

输出格式

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 .

输入输出样例

输入样例 #1

2 2 0.500000
1 2

输出样例 #1

3.250000000

输入样例 #2

4 3 0.4
4 3 1 2

输出样例 #2

6.631200000

说明

Consider the first example, we have 2 trees with height 2.  There are 3 scenarios: 1. Both trees falls left. This can either happen with the right tree falling left first, which has  probability (also knocking down the left tree), or the left tree can fall left and then the right tree can fall left, which has  probability. Total probability is . 2. Both trees fall right. This is analogous to (1), so the probability of this happening is . 3. The left tree fall left and the right tree falls right. This is the only remaining scenario so it must have  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 .