Верёвочный мост

Одна из самых известных задач с собеседований в Microsoft.

Четыре путника должны ночью переправиться по шаткому верёвочному мосту на другой берег реки. Мост настолько ненадёжен, что одновременно идти по нему могут только два человека, и только с фонариком. К сожалению, у них всего один фонарик на четверых.

Каждый из путников может пересечь мост со своей скоростью. Первый делает это за 1 минуту, второй за 2 минуты, третий за 5 минут, четвёртый за 10 минут. Если по мосту вместе идут два человека, то они движутся со скоростью самого медленного из них.

За какое минимальное время путники могут переправиться через реку? Ответ "19 минут" неправильный.

Решение
Путники могут переправиться на другой берег за 17 минут. Главная идея - сделать так, чтобы двое самых медленных шли вместе.

1. Первый и второй переходят на другой берег - 2 минуты
2. Первый возвращается с фонарём один - 1 минута
3. Третий и четвёртый переходят на другой берег вместе - 10 минут
4. Второй возвращается с фонарём за первым - 2 минуты
5. Первый и второй переходят мост в последний раз - 2 минуты
Итого: 17 минут.