Задача

venom1996

Новичок
Собственно вот задача "На одной стороне реки 4 человека бегут по картофельному полю от оборотней к реке и хотят перебраться на другую сторону за минимальное время. Все они двигаются с разной скоростью и проходят мост один за 2, другой за 3, 6 и 12 мин соответственно. Мост выдерживает только 2 человек одновременно. На мосту нет некоторых дощечек, поэтому по нему можно идти только с фонариком, который один на всех. За какое минимальное время все люди могут перебраться на другую сторону?"
Ваши догадки ?
 

fixxxer

К.О.
Партнер клуба
Вариация на тему волка-козы-капусты. :)

Тут и гадать не надо, решается динамическим программированием. Можно найти обобщенный алгоритм для всей серии задач (generalized river crossing puzzle).
 
Последнее редактирование:

WMix

герр M:)ller
Партнер клуба
12+(2 с фонариком назад) + 6+2 +3 = 25 минут
 

Valick

Новичок
WMix, как Вы себе это представляете? Для того что бы переходить мост с одним фонариком на двоих, скорость должна быть одинаковая. Скорость у всех разная, следовательно при каждом проходе один из двоих падает в воду.
 

WMix

герр M:)ller
Партнер клуба
я это представляю так, тот кто может пройти за 2 минуты, может замедлить темп и пройти за 12 дабы помочь.
 

Valick

Новичок
WMix, это уже домыслы, в ТЗ ничего про замедление темпа не сказано (и я на 100% уверен никакого замедления быть не должно). Так можно сказать, что и тот кто идёт за 12 минут может ускорится, а то и побежать с "неистовой силою", а еще двое могут взять на руки двоих других и так далее.
Здесь галимое условие с поправками на ветер. Единственное логическое объяснение - это то, что фонарик находящийся на мосту освещает весь мост не зависимо от того в чьих руках он находится. Если бы я писал условие, то сказал бы к примеру, что мост освещается только тогда когда на нём находится 2 человека одновременно. Тогда пока один человек идёт 12 минут по мосту, второй который идёт 6 минут успевает сходить туда и назад тем самым выполняя оба условия ограничение моста на количество человек и количество человек необходимых для освещения освещение, и так далее.
Есть подобная задача про тоннель и факел, что более правдоподобно с точки зрения освещения.
http://brainden.com/golovolomki/crossing-river.htm
 

WMix

герр M:)ller
Партнер клуба
останемся терпимыми к инакомыслящим
 

Фанат

oncle terrible
Команда форума
WMix, как Вы себе это представляете? Для того что бы переходить мост с одним фонариком на двоих, скорость должна быть одинаковая. Скорость у всех разная, следовательно при каждом проходе один из двоих падает в воду.
ок, а твой алгоритм?
 

Valick

Новичок
Фанат, честно говоря нет времени, но навскидку думаю 12-минутный сходит два раза туда и один оттуда. Хотя может быть есть и более оптимальный вариант.
 

Valick

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

Valick

Новичок
у них скорости разные же
почитайте внимательнее, пока один более медленный идёт от одного края до другого края, второй более быстрый ходит туда обратно, главное что бы время одно относительно другого было кратное, по факту в любой момент времени на мосту будет двое, не больше (что бы мост не рухнул) и не меньше (что бы свет горел). Например первый идёт 12 минут, второй 6 минут туда и 6 минут обратно.
 

Valick

Новичок

Valick

Новичок
WMix, ещё раз повторюсь в описании задачи ничего не сказано о том, что человек может идти медленнее.
Мост выдерживает только 2 человек одновременно.
и ничего не сказано, о том что мост может выдержать одного человека ;)
Правильно сказал MiksIr не пускайте меня к программированию, пока не научитесь писать ТЗ :)
 
Сверху