Может уже было...

Задача из ряда "решите на собеседовании при найме на работу"

Есть мост через реку. Пропускная способность, не более двух человек.
Четыре человека различной мобильности. Преодолевают мост за:
первый 1 мин (на велике)
второй 2 мин (на роликах)
третий 5 мин (простой пешеход)
четвертый 10 мин (ну калека наверное совсем).
Есть так же фонарик, один на всех. (Дело конечно происходит ночью).

ну и задача конечно перейти всем через мост.

Переходить можно по одному либо парами. Обязательно с собой иметь фонарик. (Т.е. фонарик придется таскать туда сюда)
Если идут вдвоем, то конечно скорость преодоления моста равна скорости более медленного человека.

задача перейти за минимальное время.

Подсказка: 19 мин не ответ.

Здравствуйте, Ыукпун, Вы писали:

Ы>Может уже было...

Поискал хорошенько. Оказывается точно была. И не один раз...
Эх...

P.S. Единственное, что уже более полугода прошло. Может кому и понравится кто не видел...

Здравствуйте, Ыукпун, Вы писали:

Ы>задача перейти за минимальное время.
для начала сажаем калеку на велосипед, таким образом задача из [1,2,5,10] сводится к [1,2,5,5] (бывший велосипедист теперь пешком)...

а подходят все к мосту с одной стороны?
если с разных то минимальное время имхо 12 мин (если при этом калека на велосипеде, то 7 мин)

Ы>Подсказка: 19 мин не ответ.

Если считать, что все с одной стороны моста, то 17 минут.

— сначала 5, 2 идут вместе
— 1 едет за фонариком и возвращается обратно
— 10 и 1 идут на другую сторону

в итоге все перешли за 17 минут.

Здравствуйте, Ыукпун, Вы писали:

Ы>Может уже было...

Ы>Задача из ряда "решите на собеседовании при найме на работу"

Ы>Есть мост через реку. Пропускная способность, не более двух человек.
Ы>Четыре человека различной мобильности. Преодолевают мост за:
Ы>первый 1 мин (на велике)
Ы>второй 2 мин (на роликах)
Ы>третий 5 мин (простой пешеход)
Ы>четвертый 10 мин (ну калека наверное совсем).
Ы>Есть так же фонарик, один на всех. (Дело конечно происходит ночью).

Ы>ну и задача конечно перейти всем через мост.

Ы>Переходить можно по одному либо парами. Обязательно с собой иметь фонарик. (Т.е. фонарик придется таскать туда сюда)
Ы>Если идут вдвоем, то конечно скорость преодоления моста равна скорости более медленного человека.

Ы>задача перейти за минимальное время.

Ы>Подсказка: 19 мин не ответ.

Вот здесь (Задача 6. Олимпиада.) полная задача. Я в свое время ее даже решил

Здравствуйте, Jax, Вы писали:

Jax>Если считать, что все с одной стороны моста, то 17 минут.

Jax>- сначала 5, 2 идут вместе
Jax>- 1 едет за фонариком и возвращается обратно

Куда он идет? У него то фонарика нет.

Jax>- 10 и 1 идут на другую сторону

Jax>в итоге все перешли за 17 минут.

                     1 2 5 10 -----  null
1 и 2  -> 2 минуты   5 10     -----  1 2
1      <- 1 минута   1 5 10   -----  2
5 и 10 -> 10 минут   1        -----  2 5 10
2      <- 2 минуты   1 2      -----  5 10
1 2    -> 2 минуты   null     -----  1 2 5 10
          --------
          17 минут

Здравствуйте, Nev0, Вы писали:

N>Здравствуйте, Jax, Вы писали:

Jax>>Если считать, что все с одной стороны моста, то 17 минут.

Jax>>- сначала 5, 2 идут вместе
Jax>>- 1 едет за фонариком и возвращается обратно

N>Куда он идет? У него то фонарика нет.

У каждого велосипедиста должен быть фонарик а еще насос

Здравствуйте, Jax, Вы писали:

Jax>Здравствуйте, Nev0, Вы писали:

N>>Здравствуйте, Jax, Вы писали:

Jax>>>Если считать, что все с одной стороны моста, то 17 минут.

Jax>>>- сначала 5, 2 идут вместе
Jax>>>- 1 едет за фонариком и возвращается обратно

N>>Куда он идет? У него то фонарика нет.

Jax>У каждого велосипедиста должен быть фонарик а еще насос

тогда 12 минут хватит:
фонарик даем "калеке" и "пешеходу", а велосипедист своим фонариком подсветит челу на роликах

Jax>Если считать, что все с одной стороны моста, то 17 минут.

Jax>- сначала 5, 2 идут вместе
Jax>- 1 едет за фонариком и возвращается обратно
ага только по дороге он падает за борт так как дороги не видит, фонарик то 5 и 2 с собой на той стороне держут!
Jax>- 10 и 1 идут на другую сторону

Jax>в итоге все перешли за 17 минут.
в итоге калека ждет до бесконечности потому что велосипедиста превратился в утопленника и его скорость передвижения равна скорости течения реки да к тому же в с сторону от моста

Здравствуйте, _JoKe_, Вы писали:

_JK>в итоге калека ждет до бесконечности потому что велосипедиста превратился в утопленника и его скорость передвижения равна скорости течения реки да к тому же в с сторону от моста

Можно так. Велосипедист и товарищ на роликах едут на другой конец моста. Затем они залазят друг на друга (с велосипеда и ролика придётся слезть, иначе конструкция получается неустойчивой), и тот, который наверху один раз включает и выключает фонарик — это команда калеке и пешеходу — мол всё, пошли, ребята. Затем товарищ с фонариком изображает маяк, а пешеход с калекой держась за руку идут по направлению к источнику света. И безопасно, и в 12 минут уложатся

Здравствуйте, Ыукпун, Вы писали:


Ыукпун это круто......
Sergey

Здравствуйте, Ыукпун, Вы писали:

Ы>Может уже было...

Кстати, я так понимаю, подобный тип задач не имеет четкого алгоритма решения и решается:

1) либо с помощью интуиции
2) либо перебором всех вариантов.

По крайне мере, я не вижу, как составить целевую функции, минимум которой следует найти.
Так?

И еще один вопрос, насчет перебора. А реально программу, которая переберет все варианты ? Я тут попробовал представить, ничего путного не вышло...

Пусть есть N человек (N >= 2), время перехода моста каждым из них соответственно Ti, 1 <= i <= N. Пускай они также отсортированы по возрастанию.

Для случая с одним фонариком вырисовывается такой алгоритм...

Обозначим исходный берег А, целевой — Б.

[*] На берег Б отправляются двое с минимальным временем (обозначим их как Tmin1, Tmin2)
[*] На берег А возвращается один с минимальным временем (т.е. Tmin1)

Далее выполнять в цикле, пока на берегу А всё ещё остались люди {
   [*] На берег Б отправляются двое с максимальным временем (обозначим их как Tmax1, Tmax2)

   [*] Если на берегу А ещё остались люди, то {
       [*] На берег А возвращается один с минимальным временем.

       [*] Если Tmin1+2*Tmin2 < Tmin_на_берегу_Б, то {
           [*] На берег Б отправляются двое с минимальным временем
           [*] На берег А возвращается один с минимальным временем
       }
   }
}

Здравствуйте, Ыукпун:
Как Вам такой ответ:
Велосипедист и роллер — туда;
велосипедист с роликами (но без роллера) — обратно;
калеку на ролики и на прицеп к велосипедисту — надр берег;
и тд.
вроде за 8мин управятся

Здравствуйте, Ыукпун, Вы писали:

1 + 2 -> 2
1 ret -> 1
5 + 10 -> 10
2 ret -> 2
1 + 2 -> 2

result: 17 min.

Ы>Может уже было...

Ы>Задача из ряда "решите на собеседовании при найме на работу"

Ы>Есть мост через реку. Пропускная способность, не более двух человек.
Ы>Четыре человека различной мобильности. Преодолевают мост за:
Ы>первый 1 мин (на велике)
Ы>второй 2 мин (на роликах)
Ы>третий 5 мин (простой пешеход)
Ы>четвертый 10 мин (ну калека наверное совсем).
Ы>Есть так же фонарик, один на всех. (Дело конечно происходит ночью).

Ы>ну и задача конечно перейти всем через мост.

Ы>Переходить можно по одному либо парами. Обязательно с собой иметь фонарик. (Т.е. фонарик придется таскать туда сюда)
Ы>Если идут вдвоем, то конечно скорость преодоления моста равна скорости более медленного человека.

Ы>задача перейти за минимальное время.

Ы>Подсказка: 19 мин не ответ.