#PQZ1057x5170. 加速度

    ID: 2510 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>QOJ官方数据QOJ官方测试点来源赛事1057二分答案动态规划

加速度

加速度

题目描述

标题: 加速度 - Problem - QOJ.ac

#5170. 加速度

Statistics

The problem was used in the following contests:

题目背景

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

题目描述

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

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

绝对误差或相对误差不超过 10−4 即算正确,保证对于无解的数据,即使将任意 li,ri 放大或者缩小 0.001 倍仍然无解。

输入格式

n as1 s2 … sn+1 l1 r1l2 r2…ln+1 rn+1

输出格式

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

样例数据

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≤n≤5000

1≤a≤1000

0=s1<s2<⋯<sn+1≤109

l1=0,r1=109 和 0≤li≤ri≤109

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

部分分

子任务1(30分):保证 n≤10。

子任务2(20分):保证 ri=109

子任务3(30分):保证 n≤300

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

尾声

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

官方测试点 25 个;落地 4 个;时限 1.0s,内存 1024MB。

样例

样例 1

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

样例 2

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

数据来源:QOJ 公开题包官方 .in/.out;本题落地 4 个测试点,QOJ 元数据标注官方共 25 点,覆盖级别:部分官方测试点。时限 1.0s,内存 1024MB。按 Hydro 默认逐字节比对判定。