Not an official ACM page
[Problem H
| 1995 ACM finals problem set
| My ACM problem archive
| my home page]
1995 ACM Scholastic Programming Contest Finals
sponsored by Microsoft ®
Problem G
Train Time
City transportation planners are developing a light rail transit
system to carry commuters between the suburbs and the downtown
area. Part of their task includes scheduling trains on different
routes between the outermost stations and the metro center hub.
Part of the planning process consists of a simple simulation of train
travel. A simulation consists of a series of scenarios in which two
trains, one starting at the metro center and one starting at the
outermost station of the same route, travel toward each other along
the route. The transportation planners want to find out where and when
the two trains meet. You are to write a program to determine those
results.
This model of train travel is necessarily simplified. All scenarios
are based on the following assumptions.
- All trains spend a fixed amount of time at each station.
- All trains accelerate and decelerate at the same constant
rate. All trains have the same maximum possible velocity.
- When a train leaves a station, it accelerates (at a constant
rate) until it reaches its maximum velocity. It remains at that
maximum velocity until it begins to decelerate (at the same constant
rate) as it approaches the next station. Trains leave stations with an
initial velocity of zero (0.0) and they arrive at stations with
terminal velocity zero. Adjacent stations on each route are far enough
apart to allow a train to accelerate to its maximum velocity before
beginning to decelerate.
- Both trains in each scenario make their initial departure at the
same time.
- There are at most 30 stations along any route.
Input
All input values are real numbers. Data for each scenario are in the
following format.
d1 d2 ... dn 0.0
- For a single route, the list of distances (in miles--there are
5,280 feet in a mile) from each station to the metro center hub,
separated by one or more spaces. Stations are listed in ascending
order, starting with the station closest to the metro center hub
(station 1) and continuing to the outermost station. All distances are
greater than zero. The list is terminated by the sentinel value 0.0.
v
- The maximum train velocity, in feet/minute.
s
- The constant train acceleration rate in
feet/minute².
m
- The number of minutes a train stays in a station.
The series of runs is terminated by a data set which begins with the
number -1.0.
Output
For each scenario, output consists of the following labeled data.
- The number of the scenario (numbered consecutively, starting with
scenario #1).
- The time when the two trains meet in terms of minutes from
starting time. All times must be displayed to one decimal place. Also,
if the trains meet in a station, output the station number where they
meet.
- The distance in miles between the metro center hub and the place
where the two trains meet. Distances must be displayed to three
decimal places.
Sample Input
15.0 0.0
5280.0
10560.0
5.0
3.5 7.0 0.0
5280.0
10560.0
2.0
3.4 7.0 0.0
5280.0
10560.0
2.0
-1.0
Output for the Sample Input
Scenario #1:
Meeting time: 7.8 minutes
Meeting distance: 7.500 miles from metro center hub
Scenario #2:
Meeting time: 4.0 minutes
Meeting distance: 3.500 miles from metro center hub, in station 1
Scenario #3:
Meeting time: 4.1 minutes
Meeting distance: 3.400 miles from metro center hub, in station 1
This page maintained by
Ed Karrels.
Last updated September 20, 1999