Re: Сделать четвёртого водилой


Автор сообщения: Michael
Дата и время сообщения: 24 October 2004 at 03:53:48:

В ответ на сообщение: Re: Тут я открываю алгоритм - не читать! (но ставлю вопрос об оптимальности вари

Вот какой способ сделать 4-го водилой пришёл мне в голову.

Разумеется, однобитовым сигналом не скажешь 4-му, сколько сидело до него - 1,2 или 3 разбойника. Но что если 3-й делегирует 4-му полномочия водилы только в одном, самом вероятном для данного N, случае? Например, если сидящий в 3-й день разбойник - 1-й или 2-й по счёту, то он выключает лампочку и становится водилой. А если он 3-й - он включает лампочку, и этим сигнализирует 4-му - "было трое, теперь водила ты".

В худшем случае мы не проигрываем ничего, в лучшем - выиграем ещё один круг.

Но это не предел! Эстафету можно продолжить и дальше, но на этот раз мы уже будем терять в худших (маловероятных) случаях. Зато можем выиграть много.

Итак, начало игры по новому алгоритму таково. Выбирается k: 3Бандит, попавший в карцер в первый день, зажигает лампочку. Водилой будет тот бандит, который в начальные k дней первым попадёт в карцер второй раз. Он гасит лампочку, и начинает отсчёт, зная, сколько было до него.

В худшем случае водилой (как и раньше) станет тот, кто сядет в 3-й день, и мы потеряем k-3 дней.


1811. Mihael'ю еще одна задачка! - Заметил-Просто 11:14 21.10.04 (61)
К списку тем на странице