Connection Status:
Competition Arena > GasStations

GasStations

SRM 153 · 2003-07-01 · by lars2520

SRM 153 · 2003-07-01 · by lars2520 · Search
Class Name: GasStations
Return Type: double
Method Name: tripCost
Arg Types: (vector<int>, vector<int>, int, int, int)
Problem Statement

Problem Statement

With today's high gas prices, drivers often go to great lengths to find the cheapest gas. In this problem, you are to write a method for a system that helps a person plan where to stop for gas on a long trip. You can assume that the person has already planned the route, and that it is fixed. With the route information, the system (which might be built into a car, for example) can retrieve price information about the gas at all of the gas stations along the way. With this information, your method must plan which gas stations to stop at, and how much gas to get at each station to minimize the cost of the trip.

More specifically, you will be given a int[] dist, a int[] prices, an int mpg, an int tankSize, and an int tripLength and are to return the lowest possible cost of the trip. Each element of dist, and the corresponding element of prices, represents the distance to the gas station from the start of the trip (in miles) and the price of the gas at that station (in thousandths of a dollar per gallon). mpg stands for miles per gallon, and represents the number of miles the car may travel on a single gallon of gas. Note that gallons need not be used in whole amounts. tankSize represents the maximum number of gallons that the tank of gas may hold. The trip starts at mile 0 and ends at mile tripLength, and you start the trip with a full tank of gas. You may purchase any quantity of gas (including fractional amounts of gallons) at any gas station.

Notes

  • Your solution need not be exactly correct to be evaluated as correct. As long as the relative error between your result and the true result is less than 1e-9, your result will be evaluated as correct.

Constraints

  • distances and prices will contain the same number of elements.
  • distances and prices will contain between 1 and 50 elements, inclusive.
  • mpg will be between 1 and 1000, inclusive.
  • tankSize will be between 1 and 1000, inclusive.
  • tripLength will be between 2 and 10,000, inclusive.
  • Each element of distances will be between 1 and tripLength-1, inclusive.
  • Each element of prices will be between 50 and 20,000, inclusive.
  • The trip will be possible.
Examples
0)
{100,100}
{1000,1500}
20
10
300
Returns: 5000.0

The 10 gallon tank allows the car to go 200 miles on a full tank. So, in order to get from the station at 100 miles to the end of the trip at 300 miles, the tank has to be filled up at one of the gas stations after 100 miles. Clearly, we should fill it up at the cheaper one, and since we have gone 100 miles so far, we need to buy 5 gallons of gas, for 5,000 thousandths of a dollar.

1)
{300,450,525}
{1659,1529,1439}
20
20
600
Returns: 15277.5
2)
{300,450,525}
{1659,1439,1529}
20
20
600
Returns: 14940.0
3)
{300,125,450,525}
{1659,1729,1439,1529}
20
20
600
Returns: 14940.0
4)
{200}
{1000}
20
20
400
Returns: 0.0
100)
{1500,4500}
{6000,8000}
80
40
6400
Returns: 282500.0

{1552,4580} {6773,8477} 79 40 5256

Submissions are judged against all 103 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GasStations with a public method double tripCost(vector<int> dist, vector<int> price, int mpg, int tankSize, int tripLength) · 103 test cases · 2 s / 256 MB per case

Submitting as anonymous