master
1<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
2<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->
3<HTML>
4<HEAD>
5<TITLE>Budget Travel</TITLE>
6<META NAME="description" CONTENT="Budget Travel">
7<META NAME="keywords" CONTENT="htmlatex">
8<META NAME="resource-type" CONTENT="document">
9<META NAME="distribution" CONTENT="global">
10<LINK REL=STYLESHEET HREF="htmlatex.css">
11</HEAD>
12<BODY LANG="EN" BGCOLOR=#FFFFFF>
13 <H1><BR CLEAR=ALL><CENTER><TABLE BGCOLOR=#0060F0><TR><TD><B><FONT SIZE=5 COLOR=#C0FFFF> <A NAME="SECTION0001000000000000000000">Budget Travel</A></FONT> </B></TABLE></CENTER></H1>
14<P>
15An American travel agency is sometimes asked to estimate the minimum cost
16of traveling from one city to another by automobile. The travel agency
17maintains lists of many of the gasoline stations along the popular routes.
18The list contains the location
19and the current price per gallon of gasoline for each station on the list.
20<P>
21<P>
22In order to simplify the process of estimating this cost, the agency uses
23the following rules of thumb about the behavior of automobile drivers.
24<P>
25<UL><LI> A driver never stops at a gasoline station when the gasoline tank
26contains more than half of its capacity unless the car cannot get to the
27following station (if there is one) or the destination with the amount of
28gasoline in the tank.<LI> A driver always fills the gasoline tank completely at every gasoline
29station stop.<LI> When stopped at a gasoline station, a driver will spend $2.00 on
30snacks and goodies for the trip.<LI> A driver needs no more gasoline than necessary to reach a gasoline
31station or the city limits of the destination. There is no need for a ``safety
32margin."<LI> A driver always begins with a full tank of gasoline.<LI> The amount paid at each stop is rounded to the nearest cent
33(where 100 cents make a dollar).
34</UL>
35<P>
36You must write a program that estimates the minimum amount of money that a
37driver will pay for gasoline and snacks to make the trip.
38<P>
39<H2><FONT COLOR=#0070E8><A NAME="SECTION0001001000000000000000">Input</A></FONT></H2>
40<P>
41Program input will consist of several data sets corresponding to different
42trips. Each data set consists of several lines of information. The first
432 lines give information about the origin and destination. The remaining
44lines of the data set represent the gasoline stations along the route,
45with one line per gasoline station. The following shows the exact format
46and meaning of the input data for a single data set.
47<P>
48<DL ><DT><STRONG>Line 1:</STRONG>
49<DD> One real number - the distance from the origin to the destination
50<DT><STRONG>Line 2:</STRONG>
51<DD> Three real numbers followed by an integer
52<P>
53<UL><LI> The first real number is the gallon capacity of the automobile's fuel tank.<LI> The second is the miles per gallon that the automobile can travel.<LI> The third is the cost in dollars of filling the automobiles tank in the origination city.<LI> The integer (less than 51) is the number of gasoline stations along the route.
54</UL>
55<P>
56<DT><STRONG>Each remaining line:</STRONG>
57<DD> Two real numbers
58<P>
59<UL><LI> The first is the distance in miles from the origination city to the gasoline station.<LI> The second is the price (in cents) per gallon of gasoline sold at that station.
60</UL>
61 </DL>
62<P>
63All data for a single data set are positive. Gasoline stations along a route
64are arranged in nondescending order of distance from the origin. No gasoline
65station along the route is further from the origin than the distance from
66the origin to the destination.
67There are always enough stations appropriately placed along the each route
68for any car to be able to get from the origin to the destination.
69<P>
70<P>
71The end of data is indicated by a line containing a single
72negative number.
73<P>
74<H2><FONT COLOR=#0070E8><A NAME="SECTION0001002000000000000000">Output</A></FONT></H2>
75<P>
76For each input data set, your program must print the data set number and a
77message indicating the minimum total cost of the gasoline and snacks
78rounded to the nearest cent. That total cost must include the initial cost of
79filling the tank at the origin.
80Sample input data for 2 separate data sets and the corresponding correct
81output follows.
82<P>
83<H2><FONT COLOR=#0070E8><A NAME="SECTION0001003000000000000000">Sample Input</A></FONT></H2>
84<P>
85<PRE>475.6
8611.9 27.4 14.98 6
87102.0 99.9
88220.0 132.9
89256.3 147.9
90275.0 102.9
91277.6 112.9
92381.8 100.9
93516.3
9415.7 22.1 20.87 3
95125.4 125.9
96297.9 112.9
97345.2 99.9
98-1</PRE>
99<P>
100<H2><FONT COLOR=#0070E8><A NAME="SECTION0001004000000000000000">Sample Output</A></FONT></H2>
101<P>
102<PRE>Data Set #1
103minimum cost = $27.31
104Data Set #2
105minimum cost = $38.09</PRE>
106<P>
107</BODY>
108</HTML>