ICPC Practice Set 1

Problem 1 - Refuel

You have just purchased an experimental car that runs on two different types of fuel. Besides running on gasoline, the car can run on dilithium crystals. It has two separate fuel and engine systems, one standard gasoline system and one dilithium system.

The car gets different fuel efficiency for each type of fuel, and the costs of the fuel vary from station to station. You can choose to drive on either fuel or source, and thus can modify which system you use to account for fluctuations in gas prices.

You are about to take a long trip (beginning with a full tank of gas) and want to find what the cheapest way to get to your destination is. You already know the route you will drive, and you have made a list of all fuel stations along the way. You do not need to stop at each station, but every time you do make a stop, you will have to fill up both your gasoline tank and your dilithium tank at the prices set by that station.

You can assume that it is always possible to make the trip.

Input:

You will repeatedly read in scenarios giving trip information.
The first line of input for a scenario will give four numbers, in order, representing:

The capacity (in gallons) of the gasoline tank
The capacity (in gallons) of the dilithium tank
The miles per gallon achieved by the gasoline engine
The miles per gallon achieved by the dilithium engine

If the capacities are both 0.0, that means you have already read all scenarios, and do not need to process any more scenarios.
The next line of input will give two numbers, first an integer giving the total number of filling stations, n, along the way, and second a number stating the distance to the final goal.
The next n lines will each contain data about a particular filling station. Each line conatins:

The distance of that station from the starting point
The cost in dollars per gallon for gasoline and for dilithium crystals.

Output:

For each scenario, output the minimum number of dollars necessary to spend to reach your destination. Output your answer to the nearest cent.

Example Input:

10.0 3.0 25.0 100.0
3 1000.0
200.0 2.50 12.00
600.0 3.50 12.00
750.0 10.0 50.0
0.0 0.0 0.0 0.0

Example Output:

$70.00

Note that you achieve this by stopping at the first and second stations. When driving to the first station, you use only your gasoline engine, using 8 gallons, costing $20.00 to refill (had you used the dilithium engine, it would be two gallons, costing $24 to refill). Going to the second station, you use your dilithium engine until it runs out (3 gallons used, costing $36 to refill at the second station), then go the rest of the way by using your gasoline engine (4 gallons used, costing $14 to refill at the second station). Thus, the total cost is $20 (gas at first station) + $36 (dilithium at second station) + $14 (gas at second station) for $70.00 total.

Problem 2 - Airline Rescheduling

You are tired of having plane flights cancelled and having to wait in line to get a new ticket issued. You decide to write a program that will find the optimal route between two airports, given some flight information.

Input:

You are to read in flight data that lists the flight information for several cases. The first line of input for each case will be the total number of airports, n. You may stop reading when a case with 0 airports is reached. The remaining lines will contain one flight per line, where each line lists the starting airport (a number from 1 to n), the ending airport (a number from 1 to n), and the cost of the trip (a positive value with two decimal places). A flight from airport 0 to 0 signifies the end of the list of flights. Your starting airport is always airport 1, and your destination airport is always airport 2. You may assume that there is always some path from airport 1 to airport 2.

You are to determine a sequence of flights that will get you from airport 1 to 2 at the lowes possible cost. To take into account the annoyance of layovers, the nth layover will "cost" $25*n. For example, if you fly from airport 1 to 5 to 3 to 4 to 2, you will have layover "penalties" of $25 for the layover at airport 5, $50 for the layover at airport 3, and $75 for the layover at airport 4.

Output:

You are to output a scheduled list of airports that gives you the lowest cost. You are to write one airport per line, starting with your origination, ending with the destination. If more than one route gives the same cost, any route will be acceptable. You should not include any other information. Each set of flights should be separated by a line consisting of a single -. Put this dash only between sets of flights (not before the first or after the last).

Example Input:

5
1 3 100.00
3 2 51.50
1 4 200.00
4 5 100.00
5 2 20.25
3 5 45.25
0 0 0.00
3
1 2 35.00
1 3 10.00
3 2 10.00
0 0 0.00
0

Example Output:

1
3
2
-
1
2

Although you did not print out the total cost, in the first case, it would have come to $176.50 ($100 to fly from 1 to 3, $25 layover at 3, $51.50 to fly from 3 to 2). A route from 1 to 4 to 5 to 2 would have cost $395.25 ($200 for 1 to 4, $25 layover at 4, $100 for 4 to 5, $50 layover at 5, $20.25 for 5 to 2). For the second case, the cost was $35 (for the flight from 1 to 2). Flying from 1 to 3 to 2 would have cost a total of $45 ($10 for each flight, $25 for the layover).