Fast Phil works the late shift and leaves his company's parking lot at
precisely 2:00 AM every morning. His route home is by a straight road
which has one or more traffic signals. Phil has always wondered if,
given the locations and cycles of each of the traffic signals, are
there velocities he can travel home without ever having to speed up or
slow down on account of a red light. You are to write a program to
satisfy his curiosity.
Your program should find all integer speeds (in miles per hour) which
can be used for Phil's trip home. Each speed is a rate (in miles per
hour) he can maintain the moment he leaves the parking lot at 2:00 AM
until he arrives home (we assume Phil has a long driveway in which to
decelerate) such that he never passes through a red signal. He is
allowed to pass throgh a signal at the exact moment it turns from
yellow to red, or at the exact moment a red signal turns green. Since
Phil is a relatively law-abiding citizen, you need only consider
speeds less than or equal to 60 mph. Likewise, Phil isn't interested
in travelling too slowly, so you should not consider speeds lower than
30 mph.
Input will consist of one or more sets of data describing a set of
traffic signals, followed by the integer -1. The first integer in
each set will contain the value N (specifying the number of
traffic signals). N will be no larger than 6. This value
will be followed by N sets of numbers, each containing values
(in order) for L, G, Y and R.
L is a positive real number indicating the location of a
traffic signal, in miles, from the parking lot. G,
Y and R are the lengths of time (in seconds) of the
green, yellow, and red periods of the corresponding traffic signal's
cycle. Phil has learned from an informant in the Highway Department
that all N traffic signals start their green period precisely
at 2:00 AM.
Output should consist of the input case number (starting with 1)
followed by a list of all valid integer speeds Phil may drive to avoid
the red signals. Consecutive integer speeds should be specified in
interval notation of the form L-H, where
L and H are the lowest and
highest speeds for the interval. Intervals of the form
L-L (that is, an interval of length 1) shold
just be written as L. Intervals should be
separated by commas. If there are no valid speeds, you program should
display the phrase No acceptable speeds. The
Expected Output below illustrates this format.
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.
Miguel A. Revilla
1999-03-24