Во-первых, по-моему, ответ здесь обязан зависеть от числа путешественников. Большее число путешественников потребует большее число помошников.
Допустим есть решение для одного путешественника. После его прохождения пустыни и возвращения всех помощников обратно. Проведение второго путешественника возможно по тому же алгоритму и т.д. В итоге время затраченное на процедуру, по этой схеме будет пропорционально количеству путешественников, но количество помощников будет стационарно. Т.к. время время не является критерием решения, то ответ задачи не зависит от количества путешественников.
Во-вторых, данная конкретная задача похоже не имеет решения. Дело в том, что никакой помошник не сможет уйти дальше чем на 7/2=3.5 дня от A, так как в противном случае он проест больше чем 7-дневный запас провизии (который несет), и от него уже не будет никакой помощи. Но от точки на расстоянии 3.5 от A сами путешественники не смогут добраться до B даже с полным 7-дневным запасом провизии.
Пример:
В момент времени t=0: 3-е человек выходят с полной провизией.
В момент времени t=2: 1 человек берет 7 еды, идет дальше. Остальные возвращаются обратно.
В момент времени t=4: 1-й достигнув точки "4-й день" возвращается. Остальные двое, придя в пункт А, запасаются провизией, и идут обратно.
В момент времени t=6: Встречаются в точке "2-й день", кол-во еды: 14-2*2+7-4=13, что достаточно что бы вернуться всем троим назад.
В результате один побывал в точке "4-й день", и все благополучно вернулись обратно.
Немного хитрее алгоритм для 3-х человек отправляет с возвращением на 6,3 день, но и он не является оптимальным.
В-третьих, такие задачи (см. например еще
задачу Jeep) решаются с конца: для заданного количества путешественников/помошников нужно определить максимальное расстояние, которое эти петешественники смогут пройти. Обычно это максимальное расстояние удовлетворяет некоторому рекуррентному соотношению и для него можно найти формулу. Из нее же потом легко получается решение исходной задачи.
Я очень сомневаюсь, что возможно построить для данной задачи рекурсию в функциональном виде. Но хотя сам подход: нахождение зависимости максимального расстояния на которое сможет пройти человек от количества участвующих, не отрицаю.
Четверо.
Два человека за два дня (туда и обратно) доставят еды на десять дней на склад, находящийся на расстоянии в один день пути.
Так что стратегия может быть таковой - четыре человека создают склад еды на расстоянии одного дня пути от пункта А, одного оставляют охранником, возвращаются обратно, берут ещё порцию, хотя за время их отсутствия охранник съест еды на два дня, но они принесут, разумеется, больше, чем он съест.
Накопив достаточное количество, начинают переносить склад на расстояние в два дня пути, охранников, разумеется, двое, один охраняет старый склад, второй - новый.
И так далее, до расстояния в 6.5 дней. Здесь оставляем одного охранника, еды ему на достаточное время, еды для путешественников на 6.5 дней пути, еды всем четырём на возвращение - тоже на 6.5 дней пути. Всю остальную еду аналогичным образом тащим вперёд на расстояние в 13 дней пути (7 дней до B), только носильщик уже один и охранников двое.
Соответственно, в складе на 13 днях пути, в конце концов, должна быть еда для путешественников на 7 дней пути от этого склада до B, и еда для себя на 6.5 дней чтобы добраться до первого склада.
PS: А вообще, если совмещать функции помощников и путешественников (ишь, аристократы развелись, сами пусть всё тащат) то ответ - ноль, если путешественников трое или больше.
Вы не учли условие (хотя, я по ходу не четко выразился), что если в какой-то точке органзовали склад, то максимальная вместимость склада при одном кладовщике равна 7-ми, при 2-х равна 14-ти и т.д.
Без учета этого условия вы правы, ответ - ноль.
24.07.2009, 02:47 
