You are given numbers N and M.
N represents the distance needed to cover ( in kilometers ), M represents the volume of the petrol tank of your car. To cover 1 kilometer, you need 1liter of petrol. In the beginning your car is an a petrol station which has unlimited petrol (however you can only fill up only M liters of petrol). At the end of each kilometer there are storage tanks where you can keep as much petrol as needed (one storage tank at the end of each kilometer).
You must find a way to calculate how much petrol is needed to cover N kilometers (with minimum amount of petrol).
Now here is an example to make it more clear. For example N=4 M=3
So you can fill up 3 liters of petrol, but you need to cover 4 kilometers(which you cannot do with 3 liters). So what you do is
1) Fill up 3 liters of petrol
2) Drive 1 kilometer (so you reach the storage tank)
3) Now you are left with 2 liters of petrol
4) Keep 1 liter of petrol in the storage tank
5) Now you are left with 1 liter of petrol
6) Go back 1 kilometer and reach the petrol station
7) Fill up 3 liters of petrol.
8) Drive 1 kilometer (to the storage tank)
9) Now you have 2 liters of petrol in the tank
10) Take the 1 liter of petrol you had stored in the storage tank.
11) You now have 3 liters of petrol + you have driven 1 kilometer so you only need to go 3 more
12) Since you only need to cover 3 kilometers now, and have 3 liters in the tank, the problem is solved and the answer is 6. It's 6 because you filled up 3 liters twice.
So in the first storage tank you can fill up to a maximum of (M-2) liters. In the second you can fill up to (M-4) and so on.
Any help with finding the formula to calculate how many liters is needed?
So far I now that you need N-M amount of storage tanks.
Thanks in advance
Page 1 of 1
1 Replies - 1412 Views - Last Post: 25 April 2012 - 06:29 AM
Replies To: Very Hard C++ problem (Math Formula)
Page 1 of 1