#P18538. Passing Game
Passing Game
Passing Game
有 名足球运动员位于一条直线上,编号为 。第 名运动员的位置是 。最初,球在第 名运动员手中。
运动员不能移动,但可以互相传球,并且知道彼此的位置。他们希望让球在尽可能短的时间内到达第 名运动员。
不同运动员的踢球速度不同:第 名运动员踢出的球速度为 。因此从运动员 直接传给运动员 ,耗时为
球的运动方向至多可以改变 次。如果连续两次直接传球为 和 ,并且 位于 的同一侧(都在左边或都在右边),就算发生一次方向改变。第一次传球不算改变方向。
请计算让球到达第 名运动员所需的最短时间。
输入格式
第一行一个整数 ,表示测试用例数。随后依次给出 个测试用例,每例三行:
- 第一行两个整数 ,分别表示运动员人数和允许改变方向的最大次数;
- 第二行 个整数 ,表示位置;
- 第三行 个整数 ,表示踢球速度的倒数。
限制:
- ;
- ;
- ;
- 同一输入文件中,所有测试用例的 之和不超过 ;
- 对每个 ,;
- 对任意 ,。
输入中的运动员编号不保证按坐标排列。
输出格式
每个测试用例输出一行,一个整数,表示最短时间。 时球已在目标运动员手中,所需时间为 。
原样例
2
4 2
3 2 1 6
3 1 1 3
2 0
1 2
1 2
7
1