Not an official ACM page
[Problem B
| 1993 ACM finals problem set
| My ACM problem archive
| my home page]
1993 ACM Scholastic Programming Contest Finals
sponsored by AT&T EasyLink Services
Problem A
Budget Travel
An American travel agency is sometimes asked to estimate the minimum
cost of traveling from one city to another by automobile. The travel
agency maintains lists of many of the gasoline stations along the
popular routes. The list contains the location and the current price
per gallon of gasoline for each station on the list.
In order to simplify the process of estimating this cost, the agency
uses the following rules of thumb about the behavior of automobile
drivers.
- A driver never stops at a gasoline station when the gasoline tank
contains more than half of its capacity unless the car cannot get to
the following station (if there is one) or the destination with the
amount of gasoline in the tank.
- A driver always fills the gasoline tank completely at every
gasoline station stop.
- When stopped at a gasoline station, a driver will spend $2.00 on
snacks and goodies for the trip.
- A driver needs no more gasoline than necessary to reach a gasoline
station or the city limits of the destination. There is no need for a
"safety margin."
- A driver always begins with a full tank of gasoline.
- The amount paid at each stop is rounded to the nearest cent (where
100 cents make a dollar).
You must write a program that estimates the minimum amount of money
that a driver will pay for gasoline and snacks to make the trip.
Input
Program input will consist of several data sets corresponding to
different trips. Each data set consists of several lines of
information. The first 2 lines give information about the origin and
destination. The remaining lines of the data set represent the
gasoline stations along the route, with one line per gasoline
station. The following shows the exact format and meaning of the input
data for a single data set.
Line 1: One real number -- the distance from the origin to the destination
Line 2: Three real numbers followed by an integer
- The first real number is the gallon capacity of the automobile's
fuel tank.
- The second is the miles per gallon that the automobile can travel.
- The third is the cost in dollars of filling the automobile's tank
in the origination city.
- The integer (less than 51) is the number of gasoline stations
along the route.
Each remaining line: Two real numbers
- The first is the distance in miles from the origination city to
the gasoline station.
- The second is the price (in cents) per gallon of gasoline sold at
that station.
All data for a single data set are positive. Gasoline stations along a
route are arranged in nondescending order of distance from the
origin. No gasoline station along the route is further from the origin
than the distance from the origin to the destination There are always
enough stations appropriately placed along the each route for any car
to be able to get from the origin to the destination.
The end of data is indicated by a line containing a single negative
number.
Output
For each input data set, your program must print the data set number
and a message indicating the minimum total cost of the gasoline and
snacks rounded to the nearest cent. That total cost must include the
initial cost of filling the tank at the origin. Sample input data for
2 separate data sets and the corresponding correct output follows.
Sample Input
475.6
11.9 27.4 14.98 6
102.0 99.9
220.0 132.9
256.3 147.9
275.0 102.9
277.6 112.9
381.8 100.9
516.3
15.7 22.1 20.87 3
125.4 125.9
297.9 112.9
345.2 99.9
-1
Output for the Sample Input
Data Set #1
minimum cost = $27.31
Data Set #2
minimum cost = $38.09
This page maintained by Ed Karrels
Last updated February 12, 2010