QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 5170. 加速度

Statistics

题目背景

小明骑自行车去上学.....

题目描述

小明去上学的路是一条直线,直线上有 $n+1$ 个关键位置,其中第 $i$ 个关键位置距离家的长度为 $s_i$ ,其中第一个关键点是家,最后一个关键点是学校。保证 $s_i < s_{i+1}$ 。

小明的自行车是这样一个装置,自行车的向前的加速度最大为 $a$ ,但是刹车装置可以使速度瞬间降至 $0$ 或比当前速度低的任意值。同时,自行车的速度必须时刻保持速度 $v\geq 0$。现在他希望尽早的到达学校,不过由于关键点上有红绿灯或是宇宙射线等因素,小明必须在时间段 $[l_i,r_i]$ 中经过第 $i$ 个关键点,现在你需要通过规划自行车的加速和减速,使得小明在满足要求的情况下最早到达学校,如果无论如何都无法到达学校,请输出 "kaibai" (不包含引号)。

绝对误差或相对误差不超过 $10^{-4}$ 即算正确,保证对于无解的数据,即使将任意 $l_i,r_i$ 放大或者缩小 $0.001$ 倍仍然无解。

输入格式

$$ \begin{align}\label{2} &n\ a & \\ &s_1\ s_2\ \dots \ s_{n+1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ &l_1\ r_1 \\ &l_2\ r_2 \\ &\dots \\ &l_{n+1}\ r_{n+1}\\ \end{align} $$

输出格式

一行一个浮点数表示答案,请注意输出的小数点后位数达到了足够的精度。

样例数据

input

4 2 
0 2 8 10 12 
0 1000000000 
2 2 
4 4 
6 7 
6 1000000000

output

6.5857864376

input

5 1 
0 1 2 3 4 5 
0 1000000000 
1 2 
2 3 
3 4 
4 5 
5 6

output

5.0000000000

数据约束

$1\leq n \leq 5000$

$1\leq a \leq 1000$

$0 = s_1 < s_2 < \dots < s_{n+1}\leq 10^9$

$l_1=0,r_1=10^9$ 和 $0\leq l_i \leq r_i \leq 10^9$

所有输入中的数均为自然数。

部分分

子任务1(30分):保证 $n\leq10$。

子任务2(20分):保证 $r_i=10^9$

子任务3(30分):保证 $n\leq300$

子任务4(20分):无额外限制。

尾声

感谢闫陈效 (chenxia25) 发现了题面以及数据里的 +∞ 个锅。

感谢程思元 (csy2005) 协助证明题解正确性。