Day 1 Question 3
Bus Schedule
Input file: bus.in
Output file: bus.out
A city contains several bus routes. Each route consists of a number
of stops and busses periodically travel among these stops. A traveller
wishes to make a journey from one stop to another, arriving no later
than a specified time. Your job is to determine the latest time the
traveller may arrive at the initial stop so as to be able to arrive
at the destination on time.
The input consists of a number of schedules. A schedule consists of
- A beginning time (an exact hour between 0 and 24).
- An ending time (an exact hour between 0 and 24).
- A number n indicating the number of stops on the route.
- A list of n stop numbers, one per line (each stop has a unique
number between 1 and 1000).
- A list of n-1 time intervals in minutes, one per line.
There are no more than 50 schedules and each schedule has no more than
50 stops. Following the last schedule is a line containing -1.
The busses operate as follows. For each schedule, the bus leaves at the
beginning time and visits its stops in order. The time interval between
the stops is as indicated in the schedule. At the last stop the bus
turns around and revisits the stops in reverse order with the same
time intervals. This process repeats until the ending time at which
time the bus returns home without visiting any more stops (passengers
on the bus at the end time are in serious trouble).
Following the schedules (and the line containing -1) are several
traveller requests. Each traveller request consists of
- the stop at which the journey begins
- the stop at which the journey ends
- the latest time at which the journey can end (hours and minutes on
two separate lines).
The last traveller request is followed by another line containing -1.
For each traveller request, print the latest time that the traveller can
be at the beginning stop and still reach the destination in time. It
will always be possible to make the trip.
Sample input
6
22
11
1
2
3
4
5
6
7
8
9
10
11
6
6
6
6
6
6
6
6
6
6
0
24
4
6
16
26
36
20
20
20
-1
1
11
15
0
1
11
14
59
11
36
15
0
-1
Output for Sample Input
14:00
12:00
13:00