#P18480. Egg Drop Challenge
Egg Drop Challenge
Egg Drop Challenge
一年一度的扔鸡蛋挑战即将开始!共有 名参与者,他们站在同一栋建筑的不同楼层。第 名参与者站在第 层,离地面的高度为 。第 层的参与者最初拿着一枚鸡蛋。大家希望在保证安全的前提下,尽快把鸡蛋送到第一层。
当第 名参与者拿着鸡蛋时,可以用任意一个介于 和 之间(含端点)的实数速度,竖直向下扔出鸡蛋。
当鸡蛋经过第 名参与者,即到达高度 时,如果此时速度不超过 ,这名参与者可以选择接住鸡蛋,也可以让它继续下落。接住鸡蛋意味着让它完全停止。只有当第一名参与者接住鸡蛋时,才算把鸡蛋安全送到第一层。
鸡蛋在下落过程中受到重力加速度 。为简化计算,假设没有空气阻力,且 。接住和扔出鸡蛋都在瞬间完成,不消耗时间。鸡蛋可以跳过任意中间楼层,无须让每个人都接住。
请计算安全把鸡蛋送到第一层所需的最短时间。如果无法做到,请报告无解。
输入格式
第一行一个整数 ,表示参与者人数,。
接下来 行,第 行包含三个整数 ,分别表示第 名参与者的高度、最大扔出速度和最大可接受的接住速度:
- ;
- ;
- 对所有 ,保证 。
输入只有一个实例,没有测试实例数 。
输出格式
如果存在满足所有条件的方案,输出一个实数,表示所需最短时间。绝对误差或相对误差不超过 的答案均被接受。
如果不存在方案,输出 。
样例 1
5
2 1 7
14 6 4
18 1 7
21 2 5
28 4 10
6.00000000000000000000
样例 2
2
1 1 4
10 5 1
-1
说明
如果鸡蛋以速度 开始下落,那么经过 秒后,其速度为 ;本题中为 。它下落的距离为 ;本题中为 。
样例 1 的一个最优方案如下。
- 第 5 名参与者以速度 扔出鸡蛋。经过 秒,它下落 米,速度为 ,第 3 名参与者可以接住它。
- 第 3 名参与者以速度 扔出鸡蛋,经过 秒,第 2 名参与者接住它。
- 第 2 名参与者以速度 扔出鸡蛋,再经过 秒,第 1 名参与者接住它。
总时间为 秒。
样例 2 中,即使第 2 名参与者以速度 扔出鸡蛋,到达第一层时速度仍大于 ,因此无法安全送达。