#P1442. 铁球落地
铁球落地
题目描述
在二维坐标系内有 个平台(定义平台是一条两端点纵坐标相同的开线段,开线段指线段两个端点不算做线段本身)和一个铁球,铁球如果下面没有物体,则每秒会下落一个单位长度。
球每次落到某个平台上后,游戏者可以选择水平向左或水平向右滚,球滚动速度是每秒 个单位长度。由于铁球的质量不太好,每次落下的高度不能超过 。
设计一种策略,使得球尽快落到地面而不被摔碎。
假设地面高度为 ,且无限宽。球体积相对平台极小,可以看作一个质点。请注意,球滚动至平台的一个端点处即可下落,不需要滚动至下一个格子。例如下图,小球在 处已经开始下落。
输入格式
第一行有两个整数,分别代表平台个数 和最大下落高度 。
第二行有两个整数 ,表示铁球起始时在坐标为 的位置。
第 到第 行,每行三个整数,第 行的整数 分别代表第 个平台的端点纵坐标 和左右端点的横坐标 。
输出格式
输出一行一个整数表示最小的坠落时间。
5 3
6 10
5 2 4
9 3 9
6 7 10
2 1 5
3 8 11
15
10 156
84 139
63 22 50
79 96 100
87 77 98
60 24 53
47 1 29
62 55 89
68 68 78
10 5 85
85 67 71
73 57 61
155
提示
数据规模与约定
对于全部的测试点,保证:
- 。
- ,。
- 对于所有的 ,保证互不相同, 与 也互不相同,且对于任意 ,保证 。
- 数据保证有解,最终答案不超过 。