Puzzle #41. Поездка

🎲 В вашей части есть небольшая самоходка с пустым баком, который вмещает всего 20 литров горючего. Также у вас есть 3 бочки с горючим, каждая бочка по 100 литров. В самоходку вмещается только одна бочка с горючим. 

Необходимо определить на какое максимальное расстояние вы сможете продвинуться на самоходке от вашей части.

Примечание: самоходка расходует 1 литр горючего на 1 км пути.

Разбор

Задачи на максимизацию пройденного расстояния, стоит решать с конца. Т.е. необходимо найти параметры, при которых вы проедите максимальное расстояние на последнем шаге. 

Последний отрезок пути

В нашем случае, самоходка может взять с собой только одну бочку горючего, также макс.вместимость ее бака равна 20 литрам.

Значит максимальное расстояние на последнем отрезке пути самоходка преодолеет с полной бочкой горючего (100 литров) и при полном баке (20 литров). Таким образом, считаем, что на последнем отрезке пути у нас должно остаться ровно 120 литров горючего. 120 литров горючего - это минимум 2 бочки и 120 км пути.

Предпоследний отрезок пути

300 литров - 120 = 180 литров - столько горючего у нас должно остаться на предпоследнем этапе. Т.е. на транспортировку горючего на посл.отрезок у нас есть (180 - 120) = 60 литров.

И для того чтобы привезти как минимум 2 бочки горючего на посл.отрезок нам необходимо выполнить минимум 3 ходки (привезти одну бочку на посл.отрезок - вернуться обратно - привезти вторую бочку на посл.отрезок).

Получаем 60 литров / 3 ходки = 20 литров на ходку. Это значит, что предпоследний участок занимает 20 км (из расчет 1км - 1 литр).

Важный момент: когда самоходка едет обратно за 2й бочкой, то она едет только с горючим, которое есть у нее в баке. Т.е. мы не можем ехать дальше, чем позволяет нам вместимость нашего бака.

Пред-предпоследний отрезок пути

На этом этапе мы знаем, что нам нужно доставить 180 литров горючего на предпоследний отрезок пути, это минимум 2 бочки. Как мы уже знаем, для транспортировки 2 бочек необходимо минимум 3 ходки. Снова получаем оптимальный маршрут по 20 км, тратим на это 60 литров. Т.е. в начале этого отрезка у нас было 180 + 60 = 240 литров горючего, это минимум 3 бочки.

Первый этап

Для того чтобы, привезти на след.отрезок 3 бочки горючего, нам необходимо сделать минимум 5 ходок (привезти 1ю бочку - вернуться - привезти 2ю бочку - вернуться - привезти 3ю бочку). Привезти на след.отрезок нам необходимо 240 литров, а всего у нас 300. Значит на первый этап мы можем потратить 60 литров на 5 ходок, а это 60/5 = 12 км.

Складываем все 4 отрезка и получаем общий максимальный маршрут для нашей самоходки: 12 + 20 + 20 + 120 = 172 км.