Мои постоянные читатели наверняка помнят, что у меня была целая серия задач из старых выпусков "Мурзилки" и других советских журналов для школьников. Каково же было моё удивление, когда почти такие же задачи (только с другими формулировками) давали на собеседовании ни куда нибудь, а в сам Google.
Вот одна из задач, которая была напечатана в сборнике "140 вопросов на собеседовании в Google" американского бизнес-тренера Льюиса Линна.
Четыре человека должны перейти через подвесной мост в кромешной темноте безлунной пасмурной ночью, чтобы попасть в деревню, в которой они живут. У них есть один фонарь, заряда которого хватит на 17 минут. Мост слишком опасный, чтобы переходить его в темноте без фонаря, можно запросто упасть и разбиться. К тому же он выдерживает вес только двоих людей.
Каждый из четырех человек двигается по мосту с разной скоростью. Один буквально пробегает его за минуту, второй проходит его быстрым шагом за 2 минуты. Третий проходит мост медленным шагом за 5 минут, а четвертый — за 10 минут. Как все четверо могут пересечь мост за 17 минут?
Понятно, что если два человека идут через мост, то, чтобы дорога была видна обоим, оба должны идти со скоростью наиболее медленного из них.
Самый первый и логичный вариант, который приходит в голову большинству, это отправлять каждого по очереди с самым быстрым, чтобы он быстрее возвращался назад.
Поэтому первыми отправляем через мост самого медленного и самого быстрого — переход займёт 10 минут. Обратно вернется только быстрый — это ещё минута. Теперь быстрый проводит через мост пятиминутного приятеля. И снова возвращается, чтобы провести через мост того, кто идет через мост 2 минуты. Но проблема в том, что 10+1+5+1 = 17. То есть на обратную дорогу им (минутному и двухминутному) заряда фонарика не хватит, и они не смогут перейти через мост. Смотри схему ниже.
Очевидно, что наша стратегия, в которой самый быстрый бегает через мост с фонариком, не работает. От того, что он будет переводить приятелей в другой последовательности ничего не изменится, фонарик всё равно потухнет раньше, чем все переберутся в деревню.
Так что надо менять стратегию. Понятно, что если бегать будет не самый быстрый, это только увеличит время и не приведет нас к решению. Биться головой об стену и говорить, что задачку невозможно решить — не вариант. От Гугла, конечно, можно такого подвоха ждать, но от "Мурзилки" нет, так что надо думать дальше.
Давайте пытаться оптимизировать решение. Когда самый медленный идет с самым быстром, мы как бы тратим впустую 9 минут. Когда идет самый быстрый и пятиминутный путник, впустую тратится 4 минуты. Плюс по минуте на возврат самого быстрого обратно дважды, итого 15 минут впустую.
Мы легко можем сократить это время, если пустим в одном заходе двух самых медленных. Тогда будет лишь 5 минут потерянного впустую времени. Но пускать их первыми не имеет смысла, потому что тогда потратится драгоценное время на возврат пятиминутного и на его повторный проход по мосту, чтобы снова попасть в деревню.
Пускать их последними тоже не целесообразно, потому что, чтоб в конце они остались вдвоем, надо, чтобы кто-то из них уже побывал в деревне и вернулся обратно, а это расточительство времени.
Остается последний вариант. Их надо пустить в середине. Поэтому план такой. Сначала идут самые быстрые — на переход тратится 2 минуты. Плюс одна минута на возврат самого быстрого — итого 3 минуты.
Теперь отправляем в путь самых медленных, они тратят на переход 10 минут и отдают фонарь двухминутному. Он быстрым шагом идет к самому быстрому, тратя на проход ещё две минуты — итого 3+10+2=15 минут. И теперь двухминутный и одноминутный приятели снова (как и на первом шаге) идут вместе в деревню через мост, тратя на это последние 2 минуты заряда фонарика.
Возможно, на схеме ниже будет понятнее.
Как вам задачка? Должен сказать, что она действительно требует применения аналитических способностей, которые есть далеко не у всех в нужном количестве, но интереснее то, что задача в Мурзилке была в каком-то смысле сложнее. В данном случае мы подгоняли решение под ответ, чтобы у нас получилось 17 минут. В Мурзилке же вопрос ставился по-другому. Нас просто спрашивали минимальное время, которое потребуется ребятам, чтобы перебраться на другой берег.
Не забываем, что у меня есть Ютуб-канал и другие соцсети (ссылки в описании канала). Пишите в комментариях, быстро ли у вас получилось решить эту задачу или нет? А вот, что ещё точно будет интересно: