856. 安全驾驶

单点时限: 2.0 sec

内存限制: 512 MB

在一单行直线测试车道中有 $n+1$ 辆自动驾驶的小车同向行驶。初始时每辆小车有各自的出发位置和恒定速度。

同时开始出发后,若后面的小车追上前面的小车,为了安全则必须降速到与前车相同的速度。最后所有小车都需要到达目的地。

最后一辆小车不想中途降速,希望全程匀速行驶,请找出最后一辆小车在满足条件(全程匀速且保证安全)的情况下最大可能的速度。

输入格式

第一行包含一个正整数 $d$ km($1 \leq d\leq 10^9$)表示最后一辆车目前离目的地的位置。

第二行包含一个正整数 $n$($1 \leq n \leq 1~000$)表示除最后一辆车外小车的数量。

第 $i+2$ ($1 \leq i \leq n$)行包含两个以空格分隔的正整数,表示第 $i$ 辆小车在最后一辆小车前方的距离 $k_i$km($0 < k_i < d$),以及他的速度 $s_i$km/h($1 \leq s_i \leq 10~000$),保证所有小车的出发位置($k_i$)各不相同。

输出格式

一行中输出最后一辆车的最大的可能速度(单位为 km/h),保留 $6$ 位小数。

样例

Input
2525
1
2400 5
Output
101.000000
Input
300
2
120 60
60 90
Output
100.000000
Input
100
2
80 100
70 10
Output
33.333333

382 人解决,548 人已尝试。

474 份提交通过,共有 2133 份提交。

2.8 EMB 奖励。

创建: 3 年,5 月前.

修改: 1 年,10 月前.

最后提交: 3 周,3 天前.

来源: N/A

题目标签