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.

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
Each remaining line: Two real numbers
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