Задачка от Микрософта

[avzel]

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

Comments

[kdv2005]

А скорость на мосту можно считать постоянной?

[avzel]

Да.

[kdv2005]

Ага, понял. Медленных нужно посылать вместе. Поэтому сначала посылаем двух шустрых вместе. Из них самый шустрый возвращается и следущей парой идут медленные. Они, перейдя, отдают фонарик второму шустрому, и он приводит первого шустрого с того берега. Как раз 17 минут.

[ntsil]

Сначала 1 и 2 на ту сторону (2 минуты), потом 1 обратно с фонариком (1 минута), 5 и 10 на ту сторону (10 минут), 2 возвращается с фонариком (2 минуты), 1 и 2 на ту сторону (2 минуты). Итого 17 минут.

По-моему, тут главная подсказка, что ЕСТЬ решение лучше 19. Хотя исходно, как мне кажется, и возникают две идеи: либо гонять самого шустрого, либо факторизовать 10 и 5.

[elentin]

Ой, ну это же детская задача "на перевозку", только чуть-чуть модифицирующая задачу про козу и капусту (добавлением времени).
Такое (или похожее) любят выдавать на собеседовании в 5 класс 1189 школы (она "при Курчатовском институте", что бы это ни значило), да и во всяких кружковских книжках она есть.

Я её знаю в варианте "мама, папа, маленький сын и бабушка подошли к мосту..."

Надо догадаться (1) запустить вместе двоих самых медленных (бабушку и внука) (2) один раз назад с фонариком бегает мама, а не папа.

(цифрами обозначаем скорость перемещения людей):
1, 2 туда 2 мин. На нужном берегу - 1, 2.
1 обратно 1 мин. На нужном берегу - 2.
5, 10 туда 10 мин. На нужном берегу - 2, 5, 10
2 обратно. 2 мин. На нужном берегу - 5, 10.
1, 2 туда. 2 мин. На нужном берегу - все.
Время: 2+1+10+2+2=17.

[avzel]

Дети и должны лучше решать. У них ещё мозги не заржавели.

[alevaj]

А шустрый не может в одиночку в темноте бегать?

[avzel]

Нет. Между прочим, уже четверо шустрых (= молодых) прислали правильные решения.

[alevaj]

Эту задачу давали на вступительном экзамене в МГУ на факультет гос. управления в 2005 г.

[avzel]

Ну вот, а могли бы в Микрософт поступить.

[imarek]

Уфф, решил, наконец-то: 1 и 2 вперед, 1 назад, 5 и 10 вперед, 2 назад, 1 и 2 вперед - ровно 17 минут ("1 назад" и "2 назад" можно поменять местами). Отличная задачка! А я думал, что будет какой-нибудь трюк вроде "перенести самого медленного на носилках".