Задача

[venom1996]

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

 

[fixxxer]

Вариация на тему волка-козы-капусты.

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

 

[venom1996]

Ответ : за пол часа :3

 

[Valick]

venom1996, хотелось бы услышать алгоритм решения этой задачи.

 

[WMix]

12+(2 с фонариком назад) + 6+2 +3 = 25 минут

 

[Valick]

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

 

[WMix]

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

 

[Valick]

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

 

[WMix]

останемся терпимыми к инакомыслящим

 

[Фанат]

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

ок, а твой алгоритм?

 

[Valick]

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

 

[Фанат]

думаю 12-минутный сходит два раза туда и один оттуда

а остальные? в воду попадают?

 

[Valick]

а остальные? в воду попадают?

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

 

[WMix]

остальные в паре с ним и с другими пройдут

у них скорости разные же

 

[MiksIr]

@WMix, это уже домыслы, в ТЗ ничего про замедление темпа не сказано

Не подпускайте его к программированию

 

[Valick]

у них скорости разные же

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

 

[WMix]

почитайте внимательнее, пока один более медленный идёт от одного края до другого края, второй более быстрый ходит туда обратно,

а с фонариком кто?

 

[Valick]

а с фонариком кто?

тот кто ходит быстрее

Единственное логическое объяснение - это то, что фонарик находящийся на мосту освещает весь мост не зависимо от того в чьих руках он находится.

 

[WMix]

аааа.... ну тогда подгляди ответ по ссылке

Есть подобная задача про тоннель и факел, что более правдоподобно с точки зрения освещения.
http://brainden.com/golovolomki/crossing-river.htm

 

[Valick]

WMix, ещё раз повторюсь в описании задачи ничего не сказано о том, что человек может идти медленнее.

Мост выдерживает только 2 человек одновременно.

и ничего не сказано, о том что мост может выдержать одного человека
Правильно сказал MiksIr не пускайте меня к программированию, пока не научитесь писать ТЗ