← 返回题目列表

Codeforces · 1408/C

C. 离散加速度

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

有一条路,长度 $$$l$$$ 米。道路起点的坐标为 $$$0$$$,道路终点的坐标为 $$$l$$$。

有两辆车,第一辆停在路的起点,第二辆停在路的尽头。他们将同时开始驾驶。第一辆车将从起点行驶到终点,第二辆车将从终点行驶到起点。

最初,他们将以每秒 $$$1$$$ 米的速度行驶。不同坐标 $$$a_1、a_2、\ldots、a_n$$$ 处有 $$$n$$$ 标志。每当两辆车中的任何一辆驶过旗帜时,该车的速度就会每秒增加 $$$1$$$ 米。

求汽车相遇(到达同一坐标)需要多长时间。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$):测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$, $$$l$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq l \leq 10^9$$$):标志的数量和道路的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ 按升序排列 ($$$1 \leq a_1 < a_2 < \ldots < a_n < l$$$)。

保证所有测试用例中$$$n$$$的总和不超过$$$10^5$$$。

输出

对于每个测试用例打印一个实数:汽车满足所需的时间。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则您的答案将被视为正确。更正式地说,如果您的答案是 $$$a$$$ 并且陪审团的答案是 $$$b$$$,则如果 $$$\frac{|a-b|}{\max{(1, b)}} \leq 10^{-6}$$$,您的答案将被视为正确。

示例

输入 #1

5
2 10
1 9
1 10
1
5 7
1 2 3 4 6
2 1000000000
413470354 982876160
9 478
1 10 25 33 239 445 453 468 477

输出 #1

3.000000000000000
3.666666666666667
2.047619047619048
329737645.750000000000000
53.700000000000000

注意

在第一个测试用例中,汽车将在坐标 $$$5$$$ 处相遇。

第一辆车将在 $$$1$$$ 秒内到达坐标 $$$1$$$,之后其速度将增加 $$$1$$$,等于每秒 $$$2$$$ 米。再过 $$$2$$$ 秒后,它将位于坐标 $$$5$$$ 中。因此,$$$3$$$ 秒后它将到达坐标 $$$5$$$。

第二辆车将在 $$$1$$$ 秒后到达坐标 $$$9$$$,之后其速度将增加 $$$1$$$,等于每秒 $$$2$$$ 米。再过 $$$2$$$ 秒后,它将位于坐标 $$$5$$$ 中。因此,$$$3$$$ 秒后它将到达坐标 $$$5$$$。

在 $$$1$$$ 秒后的第二个测试用例中,第一辆车将位于坐标 $$$1$$$ 中,速度等于每秒 $$$2$$$ 米,第二辆车将位于坐标 $$$9$$$ 中,速度等于每秒 $$$1$$$ 米。因此,他们将在 $$$\frac{9-1}{2+1} = \frac{8}{3}$$$ 秒后相遇。因此,答案等于 $$$1 + \frac{8}{3} = \frac{11}{3}$$$。