#P1946. Cow Cycling
Cow Cycling
题目描述:
奶牛自行车队由 ()名自行车骑手组成。它们希望确定一种比赛策略,能让其中一名骑手以最快的速度冲过终点线。和其他所有人一样,奶牛们成群结队地骑自行车比赛,因为这是抵御风阻最有效的方式。当以 圈每分钟(始终为整数)的速度行进时,队伍前方的领头奶牛每分钟消耗 单位的能量,而队伍中其余跟在它后面的奶牛每分钟仅消耗 单位的能量。更换领头奶牛不需要花费时间,但只能在整数分钟后进行。当然,奶牛们可以在任何时候退出比赛。奶牛们参加了一场 () 圈的比赛。每头奶牛都拥有相同的初始能量,即 ()单位。那么最快可能的完赛时间是多少呢?只需要有一头奶牛冲过终点线即可。完赛时间是一个整数。在某一分钟内骑过终点线和在下一分钟刚开始时勉强到达终点线没有区别(不过奶牛必须有足够剩余的能量来骑完整整一分钟)。 均为整数。
输入:
输入一行包含三个整数:。
输出:
输出一行,包含一个整数,该整数表示速度最快的奶牛能够达到的最快完赛时间。如果奶牛们的体力不足以完成比赛,则输出。
输入数据1
3 30 20
输出数据1
7
提示:
leader E
pack total used this
time leader speed dist minute
1 1 5 5 25
2 1 2 7 4
3 2* 4 11 16
4 2 2 13 4
5 3* 3 16 9
6 3 2 18 4
7 3 2 20 4
* = leader switch
来源:
美国计算机奥林匹克竞赛(USACO)2002 年 2 月赛 。