Третья задача с YaC2013. Четыре путника в Сахаре.

29.12.2013

Марина Лебедева

Это третья задача, которую мы решаем в рамках тематики «ШАД на Yet another Conference 2013».

решение первой задачи

решение второй задачи

Итак, приступим.

Четыре путника в Сахаре

4 исследователя запаслись 40 пайками и отправляются в экспедицию в Сахару. Каждый может нести запас провианта и воды на 10 дней. Цель экспедиции — наиболее далеко продвинуться в глубь пустыни, т.е. хотя бы один исследователь должен продвинуться как можно дальше, и все они должны вернуться к пункту старта. Путешественники совершают переходы в течение дня, а вечером могут передавать друг другу провиант, а также строить хранилища пайков. Как далеко сможет пробраться экспедиция (в пересчете на дневные переходы)?

Ключевые моменты в условии задачи следующие:

1. Путники могут передавать пайки;

2. Путники могут оставлять пайки в хранилище;

3. На максимальное расстояние могут продвинуться не все, т.е. некоторые могут начать путь обратно и раньше;

4. Все должны вернуться.

Мы определились с условиями и теперь нам легче решить эту задачу. Исходя из ключевых моментов можно сделать вывод, что пайки для нас очень ценные и мы не должны потратить ни одного лишнего. Это может получиться только тогда, когда мы продвигаемся вперёд, забираем пайки у одного, отдаём другим и как только наступает момент, что у путника осталось пайков только на обратный путь или дальнейшее движение будет нам нецелесообразно, то отправляем его обратно к старту.

Если помнить этот несложный принцип, то задача решается довольно просто.


В итоге получается, что путники могут продвигаться в глубь Сахары в пересчёте на дневные переходы в течение 10 дней.

  • Общее

Комментарии

Добавить комментарий

Вы вернулись, чтобы дочитать статью? Кликните на меня, я найду то место, где вы остановились.