ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1113. Джип

Explanation
Послано Denis 21 янв 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
Послано Denis Koshman 24 июл 2008 19:55
I'd like to know as well...
Re: Explanation
Послано elmariachi1414 (TNU) 25 июл 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
Послано Seraphy 16 авг 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
Послано Dmitry "Logam" Kobelev [TSOGU] 30 янв 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
Послано Nikola Yolov 30 апр 2009 22:51
Thank you for the explanation, everything is clear now.