Commit 3299f17
Changed files (1)
doc/dynamic_programming_222.html
@@ -0,0 +1,108 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
+<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->
+<HTML>
+<HEAD>
+<TITLE>Budget Travel</TITLE>
+<META NAME="description" CONTENT="Budget Travel">
+<META NAME="keywords" CONTENT="htmlatex">
+<META NAME="resource-type" CONTENT="document">
+<META NAME="distribution" CONTENT="global">
+<LINK REL=STYLESHEET HREF="htmlatex.css">
+</HEAD>
+<BODY LANG="EN" BGCOLOR=#FFFFFF>
+ <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>
+<P>
+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.
+<P>
+<P>
+In order to simplify the process of estimating this cost, the agency uses
+the following rules of thumb about the behavior of automobile drivers.
+<P>
+<UL><LI> 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.<LI> A driver always fills the gasoline tank completely at every gasoline
+station stop.<LI> When stopped at a gasoline station, a driver will spend $2.00 on
+snacks and goodies for the trip.<LI> 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."<LI> A driver always begins with a full tank of gasoline.<LI> The amount paid at each stop is rounded to the nearest cent
+(where 100 cents make a dollar).
+</UL>
+<P>
+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.
+<P>
+<H2><FONT COLOR=#0070E8><A NAME="SECTION0001001000000000000000">Input</A></FONT></H2>
+<P>
+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.
+<P>
+<DL ><DT><STRONG>Line 1:</STRONG>
+<DD> One real number - the distance from the origin to the destination
+<DT><STRONG>Line 2:</STRONG>
+<DD> Three real numbers followed by an integer
+<P>
+<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.
+</UL>
+<P>
+<DT><STRONG>Each remaining line:</STRONG>
+<DD> Two real numbers
+<P>
+<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.
+</UL>
+ </DL>
+<P>
+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.
+<P>
+<P>
+The end of data is indicated by a line containing a single
+negative number.
+<P>
+<H2><FONT COLOR=#0070E8><A NAME="SECTION0001002000000000000000">Output</A></FONT></H2>
+<P>
+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.
+<P>
+<H2><FONT COLOR=#0070E8><A NAME="SECTION0001003000000000000000">Sample Input</A></FONT></H2>
+<P>
+<PRE>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</PRE>
+<P>
+<H2><FONT COLOR=#0070E8><A NAME="SECTION0001004000000000000000">Sample Output</A></FONT></H2>
+<P>
+<PRE>Data Set #1
+minimum cost = $27.31
+Data Set #2
+minimum cost = $38.09</PRE>
+<P>
+</BODY>
+</HTML>