avzel: (Default)
[personal profile] avzel
Мне рассказали, что на собеседовании при поступлении на работу в Микрософт задают такую задачку. Группа из четырех человек подошла к подвесному мостику и желает перебраться на другую сторону. Мостик может выдержать не больше двух человек. Кроме того, дело происходит ночью, и передвигаться по мостику можно только в непосредственной близости от фонарика, а он у них - один на всех. Передвигаясь в одиночку, одному из них требуется 1 минута на переход, второму - 2, третьему - 5, и последнему - 10. Если заставить самого шустрого переходить с каждым из остальных, а затем бежать обратно с фонариком, им понадобится, как легко убедиться, 19 минут (2 + 5 + 10 туда и два рейса по минуте - обратно). Вопрос: можно ли ускорить этот процесс до 17 минут?.

Я решил эту задачу только после некоторой подсказки. А вы? Comments screened.

Update: многие прислали правильные решения и массу дополнительной интересной информации. Всем спасибо. Комменты раскрываю, так что если кто-то ещё хочет сам порешать, не заглядывайте в них.

Date: 2007-10-03 03:47 am (UTC)
From: [identity profile] kdv2005.livejournal.com
А скорость на мосту можно считать постоянной?

Date: 2007-10-03 04:08 am (UTC)
From: [identity profile] kdv2005.livejournal.com
Ага, понял. Медленных нужно посылать вместе. Поэтому сначала посылаем двух шустрых вместе. Из них самый шустрый возвращается и следущей парой идут медленные. Они, перейдя, отдают фонарик второму шустрому, и он приводит первого шустрого с того берега. Как раз 17 минут.
(deleted comment)

Создателю этого убожества

Date: 2008-10-09 05:16 pm (UTC)
From: [identity profile] kdv2005.livejournal.com
Прекратите засорять журналы живых людей!
Если уж так не терпится робота в ЖЖ выпустить, замкните их друг на друга и пусть переписываются до второго пришествия.

Date: 2007-10-03 05:06 am (UTC)
From: [identity profile] ntsil.livejournal.com
Сначала 1 и 2 на ту сторону (2 минуты), потом 1 обратно с фонариком (1 минута), 5 и 10 на ту сторону (10 минут), 2 возвращается с фонариком (2 минуты), 1 и 2 на ту сторону (2 минуты). Итого 17 минут.

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

Date: 2007-10-03 05:17 am (UTC)
elentin: (kashin-myshkin)
From: [personal profile] 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.

Date: 2007-10-03 08:08 pm (UTC)
From: [identity profile] avzel.livejournal.com
Дети и должны лучше решать. У них ещё мозги не заржавели.

Date: 2007-10-03 05:34 am (UTC)
From: [identity profile] alevaj.livejournal.com
А шустрый не может в одиночку в темноте бегать?

Date: 2007-10-03 12:47 pm (UTC)
From: [identity profile] avzel.livejournal.com
Нет. Между прочим, уже четверо шустрых (= молодых) прислали правильные решения.

Date: 2007-10-03 05:43 pm (UTC)
From: (Anonymous)
Эту задачу давали на вступительном экзамене в МГУ на факультет гос. управления в 2005 г.

Date: 2007-10-03 08:06 pm (UTC)
From: [identity profile] avzel.livejournal.com
Ну вот, а могли бы в Микрософт поступить.

Date: 2008-10-09 03:01 pm (UTC)
From: [identity profile] davidgruen.livejournal.com
Захмелевшего коменданта обнаружили не рабочие, а один шустрый бычок.

Date: 2007-10-03 12:22 pm (UTC)
From: [identity profile] imarek.livejournal.com
Уфф, решил, наконец-то: 1 и 2 вперед, 1 назад, 5 и 10 вперед, 2 назад, 1 и 2 вперед - ровно 17 минут ("1 назад" и "2 назад" можно поменять местами). Отличная задачка! А я думал, что будет какой-нибудь трюк вроде "перенести самого медленного на носилках".

Date: 2007-10-03 01:43 pm (UTC)
From: [identity profile] dklein.livejournal.com
Я давал её здешним школьникам на кружке (6-8 кл), многие решили.

Date: 2007-10-03 08:05 pm (UTC)
From: [identity profile] avzel.livejournal.com
Школьники и должны быстрее соображать.

Date: 2007-10-03 01:56 pm (UTC)
From: [identity profile] potap.livejournal.com
А я эту задачу решил только после того, как один уважаемый мною человек сказал, что она имеет решение. Такая вот была подсказка.

Date: 2007-10-03 02:07 pm (UTC)
From: [identity profile] tagdghaca.livejournal.com
сначала одноминутный и двухминутный вместе, потом одноминутный назад, пятиминутный и десятиминутный вместе, двухминутный назад, и наконец одноминутный и двухминутный вместе.

Date: 2007-10-03 03:08 pm (UTC)
elentin: (goblet)
From: [personal profile] elentin
Кстати, вспомнила ещё "японскую" модификацию (где-то с год назад пролетало по жж).
Например, здесь можно посмотреть. (Или google query)

Есть река. На одном берегу - мама, папа, два сына, две дочки, преступник и полицейский. Нужно перевезти всех на другой берег, при этом нельзя, чтобы:
- дочки оставались с папой без мамы
- сыновья оставались с мамой без папы
- преступник оставался с другими людьми без полицейского
Ещё дети не могут сами управлять плотом, плот выдерживает двух человек.

Но тут уже очень много всего, просто на бумажке по словесному описанию решать немножко непросто. Поэтому, видимо, задачка в виде флеш-картинки.

Date: 2007-10-03 05:23 pm (UTC)
From: [identity profile] relf.livejournal.com
http://www.math.temple.edu/~zeilberg/mamarim/mamarimhtml/u2.html

Date: 2007-10-03 08:04 pm (UTC)
From: [identity profile] avzel.livejournal.com
Спасибо за ссылку.

Date: 2007-10-04 07:00 pm (UTC)
From: [identity profile] vitum.livejournal.com
Слушай, это просто даже для меня. Просто не суммировать 10+5, пустить их вместе, для чего сначала отправить быстрых. Правда, мне в Микрософт уже поздно.
Page generated Jun. 23rd, 2017 12:12 pm
Powered by Dreamwidth Studios