← 返回题目列表

Codeforces · 596/D

D. 威尔伯和树木

中文机器翻译题面 查看原题

小猪威尔伯真的很想成为一只海狸,所以他今天决定假装自己是一只海狸,咬树把它们砍倒。

有 n 棵树位于一条线上的不同位置。树 i 位于位置 xi。树的所有给定位置都是不同的。

树是相等的,即每棵树的高度为 h。由于风的原因,当一棵树被砍倒时,它要么以 p 的概率向左倒下,要么以 1 - p 的概率向右倒下。如果一棵树在倒下时撞到另一棵树,则该树将以与撞到它的树相同的方向倒下。只有当两棵树之间的距离严格小于 h 时,一棵树才能撞到另一棵树。

例如,假设有 4 棵树位于位置 1、3、5 和 8,而 h = 3 并且位置 1 的树向右倒。它撞到了位置 3 的树,并且也开始掉落。反过来,它撞到了位置 5 的树,并且也开始掉落。 8和5之间的距离恰好是3,所以位置8的树不会倒下。

只要仍然有树站立,威尔伯就会以 0.5 的概率选择最左边的站立树,或者以 0.5 的概率选择最右边的站立树。然后砍掉选定的树。如果只剩下一棵树,威尔伯总是选择它。由于地面上长满了草,威尔伯想知道在他砍倒所有树木后,地面上覆盖着倒下的树木的预计总长度,因为他担心他的食草牛朋友。请帮助威尔伯。

输入

输入的第一行包含两个整数 n (1 ≤ n ≤ 2000) 和 h (1 ≤ h ≤ 108) 以及一个实数 p (0 ≤ p ≤ 1),小数点后位数不超过六位。

输入的第二行包含 n 个整数,x1, x2, ..., xn (- 108 ≤ xi ≤ 108),无特定顺序。

输出

打印一个实数——树木全部倒下时所覆盖的地面的预期总长度。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。

即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。

示例

输入 #1

2 2 0.500000
1 2

输出 #1

3.250000000

输入 #2

4 3 0.4
4 3 1 2

输出 #2

6.631200000

注意

考虑第一个例子,我们有 2 棵高度为 2 的树。

1. 两棵树都向左倒下。这种情况可能发生在右树先向左倒下的情况下,其概率为 $$\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$$(同时撞倒左树),或者左树向左倒下,然后右树向左倒下,其概率为 $$\frac{1}{4} \cdot \frac{1}{2} = \frac{1}{8}$$。总概率为 $$\frac{1}{4} + \frac{1}{8} = \frac{3}{8}$$。

2. 两棵树都向右倒。这类似于(1),因此发生这种情况的概率为$$\frac{3}{8}$$。

3. 左树向左倒,右树向右倒。这是唯一剩下的场景,因此它的概率必须为 $$1 - \frac{3}{8} - \frac{3}{8} = \frac{1}{4}$$。

情况 1 和 2 导致总共 3 个地面单位被覆盖,而情况 3 导致总共 4 个地面单位被覆盖。因此,预期值为 $$3 \cdot (\frac{3}{8}) + 3 \cdot (\frac{3}{8}) + 4 \cdot (\frac{1}{4}) = 3.25$$。