#P1310. Nonstop Travel

Nonstop Travel

题目描述

“快手菲尔”上晚班,每天凌晨22点整准时离开公司的停车场。他回家的路线是一条笔直的公路,公路上设有一个或多个交通信号灯。菲尔一直很好奇,倘若已知每个交通信号灯的位置和周期,是否存在某些速度,能让他在回家途中无需因红灯而加速或减速。你需要编写一个程序来解开他的疑惑。

你的程序应当找出所有能让菲尔顺利回家的整数速度(单位:英里每小时)。这些速度是指他从凌晨2点离开停车场直至到家这段时间内能够保持的速度(我们假定菲尔家有一条很长的私人车道供他减速),且在此速度下他不会在红灯时通过信号灯。他被允许在信号灯从黄灯变为红灯的瞬间,或者红灯变为绿灯的瞬间通过信号灯。由于菲尔是个相当遵守法律的市民,你只需考虑速度小于或等于每小时60英里的情况。同样地,菲尔也不想开得太慢,所以你无需考虑低于每小时30英里的速度。

输入

输入将由一组或多组描述交通信号灯的数据集组成,最后以整数 1-1 作为结束标志。每组数据的第一个整数为N N(表示交通信号灯的数量),NN 不超过 66。这个数值后面会跟着N N 组数据,每组数据按顺序包含 LLGGYYRR 的值。LL 是一个正实数,表示某个交通信号灯距离停车场的英里数。GGYY RR 分别是相应交通信号灯周期中绿灯、黄灯和红灯的时长(单位:秒)。菲尔从公路部门的一个线人那里得知,所有 NN 个交通信号灯都在凌晨22点整准时亮起绿灯。

输出

输出应包含输入数据的案例编号(从1 1 开始),后面跟着菲尔为避开红灯可以行驶的所有有效整数速度的列表。连续的整数速度应以区间表示法的形式“L-H”给出,其中L L HH 分别是该区间的最低和最高速度。对于“L-L”这种形式(即区间长度为 1)的区间,应直接写成L L。区间之间用逗号分隔。如果不存在有效速度,你的程序应显示“没有可接受的速度。” 下面的“预期输出”展示了这种格式。

输入示例

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年北美中北部地区竞赛