Loading...
Loading...
Loading...
A delivery rider covers a circular route with n petrol pumps, numbered 1 to n in the order he rides past them. At pump i he can fill p[i] litres. From pump i to the next pump is d[i] km, and from pump n the road goes back to pump 1. The bike uses exactly 1 litre per km, and the tank is large enough for any amount.
The rider starts at one pump with an empty tank, fills up at every pump he reaches, and must come back to the starting pump without running out on the way. Arriving at a pump with exactly 0 litres is fine. Print the smallest pump number he can start from, or -1 if no start works.
-1.Example 1
Input
4 4 6 7 4 6 5 3 5
Output
2
From pump 1 the rider has 4 litres for 6 km. From pump 2 the tank holds 1, 5, 4 and then 2 litres after each stretch, so pump 2 works.
Example 2
Input
3 1 2 3 2 3 4
Output
-1
There are only 6 litres in total for 9 km of road, so no start works.
Try the problem first. Open one hint at a time.
If the total petrol is less than the total distance, no start can work. Otherwise some start always works.
Try riding from pump 1 and keep the tank level. Suppose the tank goes below zero on the way to the next pump after pump i.
Then no pump from your start up to pump i can be the answer, because each of them arrives at that stretch with even less petrol. Start again from pump i + 1 with an empty tank.
The tank can hold up to about 10^14 litres, so use long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor