D. Вилбур и деревья
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Свинка по имени Вилбур всегда хотел быть бобром, так что сегодня он решил притвориться бобром и грызть деревья, чтобы повалить их.

Имеется n деревьев, расположенных вдоль прямой. Дерево номер i расположено в позиции xi, при этом все позиции деревьев различны.

Все деревья обладают одинаковой высотой, равной h. Когда Вилбур прогрызает какое-либо дерево, оно падает налево с вероятностью p или направо с вероятностью 1 - p. Если, падая, дерево задевает другое дерево, то задетое дерево так же начинает падать в этом же направлении. Дерево может задеть другое дерево, только если расстояние между ними строго меньше h.

Рассмотрим следующий пример: имеются четыре дерева с координатами 1, 3, 5 и 8 соответственно, и h = 3. Дерево, стоявшее в позиции 1, падает направо и задевает дерево с координатой 3. То дерево, в свою очередь, также падает и роняет дерево с координатой 5. Расстояние между 5 и 8 равно 3, поэтому последнее дерево не будет задето и останется стоять.

Пока ещё есть стоящие деревья, Вилбур равновероятно выбирает либо самое левое, либо самое правое дерево и роняет его. Если осталось только одно дерево, то Вилбур точно уронит его. Вилбур хочет знать математическое ожидание суммарной длины участков земли, покрытых упавшими деревьями, после того, как не останется ни одного стоящего дерева. Пожалуйста, помогите Вилбуру.

Входные данные

В первой строке входных данных содержатся два целых числа n и h (1 ≤ n ≤ 2000, 1 ≤ h ≤ 108) и вещественное число p (0 ≤ p ≤ 1), записанное с использованием не более чем шести знаков после точки.

В следующей строке содержатся n целых чисел x1, x2, ..., xn ( - 108 ≤ xi ≤ 108), записанных в произвольном порядке.

Выходные данные

Выведите единственное вещественное число — математическое ожидание суммарной длины всех участков земли, покрытых деревьями, когда они все упадут. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.

А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если .

Примеры
Входные данные
2 2 0.500000
1 2
Выходные данные
3.250000000
Входные данные
4 3 0.4
4 3 1 2
Выходные данные
6.631200000
Примечание

Рассмотрим пример, у нас два дерева с высотой 2.

Есть три варианта развития событий:

1. Оба дерева упадут налево. Либо правое дерево упадет налево первым с вероятностью (при этом повалив левое дерево), либо левое дерево упадет налево и затем правое дерево упадет налево, вероятность этого равна . Общая вероятность равна .

2. Оба дерева упадут направо. Это аналогично (1), так что вероятность такого события равна .

3. Левое дерево упадет налево, а правое дерево упадет направо. Это единственный оставшийся вариант, так что его вероятность должна быть .

В вариантах 1 и 2 всего будет покрыто 3 единичных отрезка земли, а в варианте 3 — 4 единичных отрезка. Следовательно, математическое ожидание равно .