#P1310. Nonstop Travel
Nonstop Travel
题目描述
“快手菲尔”上晚班,每天凌晨点整准时离开公司的停车场。他回家的路线是一条笔直的公路,公路上设有一个或多个交通信号灯。菲尔一直很好奇,倘若已知每个交通信号灯的位置和周期,是否存在某些速度,能让他在回家途中无需因红灯而加速或减速。你需要编写一个程序来解开他的疑惑。
你的程序应当找出所有能让菲尔顺利回家的整数速度(单位:英里每小时)。这些速度是指他从凌晨2点离开停车场直至到家这段时间内能够保持的速度(我们假定菲尔家有一条很长的私人车道供他减速),且在此速度下他不会在红灯时通过信号灯。他被允许在信号灯从黄灯变为红灯的瞬间,或者红灯变为绿灯的瞬间通过信号灯。由于菲尔是个相当遵守法律的市民,你只需考虑速度小于或等于每小时60英里的情况。同样地,菲尔也不想开得太慢,所以你无需考虑低于每小时30英里的速度。
输入
输入将由一组或多组描述交通信号灯的数据集组成,最后以整数 作为结束标志。每组数据的第一个整数为(表示交通信号灯的数量),不超过 。这个数值后面会跟着组数据,每组数据按顺序包含 、、 和 的值。 是一个正实数,表示某个交通信号灯距离停车场的英里数。、和 分别是相应交通信号灯周期中绿灯、黄灯和红灯的时长(单位:秒)。菲尔从公路部门的一个线人那里得知,所有 个交通信号灯都在凌晨点整准时亮起绿灯。
输出
输出应包含输入数据的案例编号(从开始),后面跟着菲尔为避开红灯可以行驶的所有有效整数速度的列表。连续的整数速度应以区间表示法的形式“L-H”给出,其中和 分别是该区间的最低和最高速度。对于“L-L”这种形式(即区间长度为 1)的区间,应直接写成。区间之间用逗号分隔。如果不存在有效速度,你的程序应显示“没有可接受的速度。” 下面的“预期输出”展示了这种格式。
输入示例
1
5.5 40 8 25
3
10.7 10 2 75
12.5 12 5 57
17.93 15 4 67
-1
输出示例
Case 1: 30, 32-33, 36-38, 41-45, 48-54, 59-60
Case 2: No acceptable speeds.
来源
1997年北美中北部地区竞赛