Про Google, Мурзилку и батарейки

В одном темном-темном лесу через бурную широкую реку с крутыми берегами перекинут шаткий мост, переходить по которому в темноте очень опасно. Больше двух человек за раз мост не выдерживает, однако одной темной-темной ночью попасть на другой берег понадобилось сразу четырем товарищам, у которых оказался всего один фонарик на всех. Как вы уже поняли, это вовсе не сценарий фильма ужасов, и даже не начало приключенческого романа, а всего лишь «загадка» из популярного советского журнала для детей «Мурзилка». Мы с вами столкнулись с классической алгоритмической задачей – ответом в этот раз будет не число, а алгоритм, то есть последовательность действий, при которой окажутся выполненными все условия задачи.

Первый из друзей перебегает мост за минуту, второму на это потребуется две, третий проходит мост за пять минут, и четвертый – за десять. Тем, кто идет вдвоем, приходится придерживаться скорости самого медленного из них. Но вот беда – в единственном фонарике садятся батарейки, поэтому переправиться через опасную реку нужно как можно скорее. Таким образом, алгоритм, который мы с вами ищем, должен быть еще и оптимальным по времени – и вот эта задача уже носит вполне математический характер.

На первый взгляд, ответ лежит на поверхности. Каждый раз фонарик нужно возвращать обратно – тем, кто мост еще не перешел, поэтому из двух дошедших до противоположного берега один должен будет пройти по мосту еще раз. Логично сделать этим «гонцом» самого быстрого – в этом случае на возвращение тратится минимальное количество времени, причем порядок, в котором тот будет переводить по мосту своих более медленных товарищей, абсолютно не важен. Суммарно переход займет 2 + 1 + 5 + 1 + 10 = 19 минут, и из них только две уйдут на походы обратно. Чтобы доказать (или опровергнуть) оптимальность такого алгоритма, обычно пришлось бы перебрать все комбинации и последовательности переходящих мост, но в этот раз у нас есть неожиданная подсказка.

Оказывается, найти эту задачу можно не только в «Мурзилке». С немного другим условием задачу опубликовал Льюис Линн в своей книге «140 вопросов на собеседовании в Google». В варианте Линна батареек фонарика хватит всего на 17 минут – воспользовавшись нашим алгоритмом, товарищи просто не успеют перейти мост, а значит где-то скрывается более быстрый способ!

Мы уже оптимизировали временные затраты на возвращение, и это не дало нужно нужного результата. Остается только присмотреться к переходам в нужную сторону: какие из них могут занимать меньше времени? Медлительные товарищи не могут идти быстрее, однако они сильно тормозят выбранного нами «гонца». Так давайте же отправим их одновременно! Проанализируем такой вариант: единственный его недостаток заключается в том, что одному из пары придется возвращаться, а значит, именно этого мы должны избежать. Нельзя отправить их первыми – пусть на противоположной стороне их уже ждет кто-то быстрый, кто сможет вернуть фонарик. Нельзя оставить их последними – это автоматически будет означать, что кто-то из них вернулся с фонарем. Итак, решено: главные тихоходы должны отправляться в середине! Но как именно мы с вами это организуем?

Первым делом отправим через мост самых шустрых: за две минуты они перейдут его в нужную сторону, первый вернется за одну минуту обратно, а второй останется ждать передачи «эстафеты». Теперь запускаем на мост третьего и четвертого товарищей: через десять минут второй из друзей возьмет у них фонарик и за две минуты вернется на исходную позицию. Осталось пересечь мост первому и второму – они справятся за еще две минуты. Теперь давайте считать: 2 + 1 + 10 + 2 + 2 = 17 минут. Мы успели!

Такой алгоритм действительно является оптимальным по времени – а значит, и решением задачи из «Мурзилки». А если вам удалось найти ответ быстрее, чем дочитать эту статью, вы по праву можете считать, что собеседование в Google прошли успешно!