PROBLEM STATEMENT
Alice wants to drive from a source city to a destination city, and being a poor
graduate student, has to make this trip as cheap as possible. One way she wants
to save money is on the gasoline for the car.
You need to help her save money. You have the following information:
- The distance between the two cities in miles.
- The capacity of her car's fuel tank in gallons.
- The mileage her car gets, in miles per gallon. Mileage of a car is the number
of miles a car covers for one gallon of gasoline.
- A list of various gas station's on the way, identified by the distance of the
station from the source city, the price of gasoline per gallon and the price of
a can of soda in that gas station.
You know that she can only fill gasoline in integral number of gallons at any
station. You also know that even though she is on a tight budget she cannot
resist the temptation of buying a can of her favorite soda at each gas station
when she stops to fill gas. Given this information you need to develop a plan
for her indicating which gas stations to stop by and how much gas to fill from
those stations, in order to minimize the total expense on gas and soda during
the trip.
Create a class GasStation that contains a method minCost, which takes the
distance of the trip, gas tank capacity of the car, the mileage the car is
capable of, and a String[] stations containing information for each gas station
on the way. minCost returns the minimum cost(for gas and soda) in cents, of
the trip.
DEFINITIONS
Class: GasStation
Parameters: int, int, int, String[]
Returns: int
Method signature (be sure your method is public): int minCost(int distance, int
tankCapacity, int mileage, String[] stations).
NOTES
- If the destination city is unreachable, return -1.
- The car gas tank is filled to capacity at the source city (free of cost)
before she begins. i.e. she begins with the full gas tank, the price of which
is to be ignored.
- Each String in the stations input parameter will be of the form "<d> <g>
<s>"(quotes and angle brackets will not be included), where:
<d> specifies the distance of the gas station from the source city.
<g> specifies the price per gallon of gas at that gas station.
<s> specifies the price of a soda can in that gas station.
- It is acceptable to reach the destination or a gas station with an empty fuel
tank. i.e. If your mileage is 20 and the destination city is 40 miles from your
current position then you can still reach the destination with exactly 2
gallons of fuel even though you will have an empty fuel tank exactly as you
reach the destination.
- The gas stations in the list will be arranged in ascending order of their
distance from the source city.
- There can be multiple gas stations at the same distance from the source city.
- The distance of each gas station will be less than or equal to the distance
of the destination city from source city, and all of the gas stations will be
on the way.
- The string represention of a number may have leading zeros. i.e. "009" is a
valid representation of number 9.
- Even though Alice can only get integral number of gallons of gasoline filled
at any station, the consumption of gasoline depends on miles covered, and hence
the amount of gasoline in the fuel tank may be non integral during travel.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- distance is between 5 and 100000, inclusive.
- tankCapacity is between 5 and 25, inclusive.
- mileage is between 5 and 25, inclusive.
- stations consists of 0 to 50 elements, inclusive.
- Each element of stations is of the form "<d> <g> <s>". A single space will
separate <d> from <g> and <g> from <s>.
- For each element of stations, <d> is between 0 and distance, inclusive.
- For each element in stations, <d> is greater than or equal to the <d> of its
predecessor element. i.e. the elements in the input parameter stations are
sorted in ascending order based on their <d> component.
- For each element of stations, <g> is between 5 and 500, inclusive.
- For each element of stations, <s> is between 5 and 500, inclusive.
EXAMPLES
Example 1
distance: 500
tankCapacity: 10
mileage: 20
stations: { "150 199 100", /*( a gas station at 150 miles with gas price of 199
cents per gallon and 100 cents for a soda)*/
"180 189 100",
"300 199 100",
"320 99 100"}
Minimum solution is: Alice gets 6 gallons (and a soda) from 2nd station (at 180
miles) & 9 gallons (and a soda) from 4th station (at 320 miles).
Minimum Cost: (6*189 + 100) + (9*99 + 100) = 2225 cents.
Hence your method should return 2225.
Example 2
distance: 300
tankCapacity: 10
mileage: 10
stations: { "50 149 100",
"100 179 99",
"150 129 100",
"200 99 101",
"250 98 109"}
Your method should return 2681.
Example 3
distance: 100
tankCapacity: 8
mileage: 5
stations: { "10 99 15",
"15 129 5",
"45 119 5",
"55 99 10",
"75 95 9"}
Your method should return 1227.
Example 4
distance: 1000
tankCapacity: 5
mileage: 5
stations: { "10 99 15",
"80 119 5"}
It is not possible to reach the destination city, as Alice will run out of
gasoline on the way. Hence your method should return -1.