← 返回题目列表

Codeforces · 309/A

A. 晨跑

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

人们喜欢保持健康。这就是为什么他们中的许多人都准备在黎明醒来,去体育场跑步。在这个问题中,你的任务是帮助一家公司设计一个新的体育场。

N市有一个破旧的旧体育场。很多人喜欢这里,每天早上都有成千上万的人来到这个体育场跑步。体育场可以用一个圆来表示,它的长度正好是l米,有一条标记的起跑线。然而,早上不能同时出发,所以正好在 7 点,每个跑步者都会前往体育场上他最喜欢的位置并从那里开始跑步。请注意,并非每个人都以与其他人相同的方式跑步。有的人是顺时针方向跑,有的人是逆时针方向跑。这主要取决于跑步者早上的心情,因此您可以假设每个跑步方向在任何固定的早晨对于每个跑步者来说都是等概率的。

体育场很小,需要大修,因为现在只有一条跑道!在一条赛道上你不能玩得太过,这就是为什么所有跑步者都保持相同的跑步速度——每个时间单位正好 1 米。然而,选择不同方向的跑步者却在相遇时相互碰撞。

该公司想要设计一个新体育场,但他们首先需要知道旧体育场有多糟糕。为此,他们需要在跑步开始后预测 t 时间单位内的碰撞次数。帮助公司计算所需的期望。请注意,每个跑步者均等概率地选择一个方向,与其他跑步者无关,然后所有跑步者在早上 7 点同时开始跑步。假设每个跑步者连续跑了 t 个时间单位而没有停止。如果跑步者发现自己位于体育场的同一点,则考虑在某个时刻发生碰撞。一对跑步者可以多次碰撞。

输入

输入的第一行包含三个整数 n、l、t (1 ≤ n ≤ 106、1 ≤ l ≤ 109、1 ≤ t ≤ 109)。下一行包含 n 个不同的整数 a1, a2, ..., an (0 ≤ a1 < a2 < ... < an < l),这里 ai 是从起始线到第 i 个跑步者的起始位置的顺时针距离。

输出

打印一个实数——绝对或相对误差最多为 10 - 6 的问题的答案。

示例

输入 #1

2 5 1
0 2

输出 #1

0.2500000000

输入 #2

3 7 3
0 1 6

输出 #2

1.5000000000

注意

第一个示例中有两个跑步者。如果第一个跑步者顺时针方向跑,那么在1个时间单位内他将距离起跑线1m。如果第二名选手逆时针方向跑,那么在1个时间单位内,他也将距离起跑线1m。这是唯一可能的见面方式。我们假设每个运行方向都是等概率的,因此示例的答案等于 0.5·0.5 = 0.25。