2000 LSU Computer Science High School Programming Contest
Problem 8: Budget Travel (Judge Copy)

MAIN
  Home
  Schedule
  Rules
  Compile

PROBLEMS
  Novice
  Veteran
  All

  

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Problem 8: Budget Travel (Judge Copy)

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 unless the car does not have enough gas to make it to the next gas station or its destination.
  • 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 cost of the trip (gasoline and snacks).

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 automobiles 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 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

Sample Output

Data Set #1
cost = $28.42
Data Set #2
cost = $38.47

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 0

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

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 0

Data Set #1
minimum cost = $28.42
Data Set #2
minimum cost = $38.47

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 1

1111.0
14.1 25.3 18.76 7
50.9 87.6
230.3 99.9
499.1 111.9
650.0 97.9
799.9 123.8
876.8 122.9
907.7 114.9
-1

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 1

Data Set #1
minimum cost = $60.46

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 2

100.1
75.5 4.3 75.50 3
5.1 119.9
50.0 125.9
76.8 101.9
-1

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 2

Data Set #1
minimum cost = $75.50

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 3

2000.0
14.8 19.7 23.86 10
265.8 35.9
500.3 47.9
750.0 40.9
800.7 49.9
1050.3 53.9
1250.0 39.8
1300.1 45.8
1550.9 56.9
1800.6 45.9
1900.7 72.9 
-1

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 3

Data Set #1
minimum cost = $82.57

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.



The statements and opinions included in these pages are those of the LSU Computer Science High School Programming Contest Staff only. Any statements and opinions included in these pages are not those of Louisiana State University or the LSU Board of Supervisors.

© 2000 LSU Computer Science High School Programming Contest

This page last updated Fri Feb 11 21:55:29 2000.