Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.
ambitious

#### GasStations

Calculate cheapest way of buying gas in order to drive along a highway.
Programming language:

There are N+1 towns numbered from 0 to N lying along a highway. The distances between towns, and gas prices in each town, are given. A truck has to deliver cargo from town 0 to town N. What is the cheapest way to buy enough gas for this trip?

Two non-empty arrays D (distances) and P (prices), each consisting of N positive integers, and a positive integer T (tank capacity) are given. Consider any sequence R (refill strategy) consisting of N non-negative integers (amount of fuel bought in each town).
Sequence L (amount of fuel when leaving town), consisting of N integers, is defined as follows:

L[K] = (R + ... + R[K]) − (D + ... + D[K−1]) for 0 ≤ K ≤ N−1

Sequence A (amount of fuel when arriving at town), consisting of N integers, is defined as follows:

A[K] = L[K−1] − D[K−1] for 1 ≤ K ≤ N

The following conditions (meaning that the truck must not run out of fuel and cannot fill up with more fuel than its tank capacity) must hold:

• 0 ≤ L[K] ≤ T for 0 ≤ K ≤ N−1
• 0 ≤ A[K] ≤ T for 1 ≤ K ≤ N

Number C (total cost of refill strategy) is defined as:

C = R * P + ... + R[N−1] * P[N−1]

For example, consider T = 15 and the following arrays D and P, consisting of three elements each:

D = 10 D = 9 D = 8 P = 2 P = 1 P = 3

Sequence [15, 10, 2] is a refill strategy with cost 46. Sequence [10, 5, 12] is not a valid refill strategy, because the truck would run out of fuel between towns 1 and 2. Sequence [10, 15, 2] is a refill strategy with cost 41, and no cheaper refill strategy exists for this choice of arrays D, P and number T.

Write a function:

class Solution { public int solution(int[] D, int[] P, int T); }

that, given two non-empty arrays D and P consisting of N positive integers each and a positive integer T, returns the cost of the cheapest refill strategy for D, P and T.
The function should return −1 if no valid refill strategy exists.
The function should return −2 if the result exceeds 1,000,000,000.

For example, given T = 15 and arrays D and P consisting of three elements each such that:

D = 10 D = 9 D = 8 P = 2 P = 1 P = 3

the function should return 41, as explained above.

Write an efficient algorithm for the following assumptions:

• T is an integer within the range [1..1,000,000];
• N is an integer within the range [1..100,000];
• each element of arrays D, P is an integer within the range [1..1,000,000].