ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1113. Jeep

Explanation
Posted by Denis 21 Jan 2008 02:41
Some helpful description can be found at
http://mathworld.wolfram.com/JeepProblem.html

But i still do not understand one thing :
For example, the farthest a Jeep with n==1 drum can travel is obviously 1 unit. However, with n==2 drums of gas, the maximum distance is achieved by filling up the Jeep's tank with the first drum, traveling 1/3 of a unit, storing 1/3 of a drum of fuel there, and then returning to base with the remaining 1/3 of a tank. At the base, the tank is filled with the second drum. The Jeep then travels 1/3 of a unit (expending 1/3 of a drum of fuel), refills the tank using the 1/3 of a drum of fuel stored there, and continues an additional 1 unit of distance on a full tank, giving a total distance of 4/3.

How this logic works with n==3 ???
Re: Explanation
Posted by Denis Koshman 24 Jul 2008 19:55
I'd like to know as well...
Re: Explanation
Posted by elmariachi1414 (TNU) 25 Jul 2008 00:57
I'll try to explain...
Suppose fuel tank capacity = 1 unit and we have 3 units of patrol at point A.
There will be three parts of the path with lengths 1/5, 1/3 and 1.
A--1/5--B------1/3------C---------------1---------------D
1. Let's carry 2 units of patrol from A to B. It would take 3 trips.
Step 0: Fuel(A) = 3, Fuel(B) = 0.
Step 1: Fuel(A) = 2, Fuel(B) = 3/5.
Step 2: Fuel(A) = 1, Fuel(B) = 6/5.
Step 3: Fule(A) = 0, Fule(B) = 10/5 = 2. And we are at B now.
2. Let's carry 1 unit of patrol from B to C. It would take 2 trips.
Step 0: Fuel(B) = 2, Fuel(C) = 0.
Step 1: Fuel(A) = 1, Fuel(B) = 1/3.
Step 2: Fuel(A) = 2, Fuel(B) = 3/3 = 1. And we are at C now.
3. Let's carry 1 unit of patrol from C to D. It would take only 1 trip.

So if we have 1-unit fuel tank and 3 litres of patrol we can travel for 1+1/3+1/5 = 23/15 km.

Good luck!
Re: Explanation
Posted by Seraphy 16 Aug 2008 21:46
when n == 1 we can travel 1 unit.
when n == 2 we will carry 1 drum as far as I can, so the situation is as same as n == 1, we can spend the extra 1 drum of gas on the way for 3 times (carry 1 , go , left some, back ,carry 1, go), so I can travel 1/3 for the best solution

when n == 3 we will carry 2 drums of gas as far as I can, then it became situation #2 , the extra 1 drum of gas will use 5 times (go , back ,go , back ,go) ,so best solution is 1/5
and so on

hope this help
Re: Explanation
Posted by Dmitry "Logam" Kobelev [TSOGU] 30 Jan 2009 11:30
You should just try to think how far you are able to move with m, 2m, 3m liters of fuel. Then it'l be easy to reform the task as moving k * m liters at the distance n1. (k is integer and n1 < m)
Re: Explanation
Posted by Nikola Yolov 30 Apr 2009 22:51
Thank you for the explanation, everything is clear now.