О выключателях ...

[borisd]

Тут либо не все начальные условия, либо не может быть решена такая задача.

Пораскинте !!!

В холле тюрьмы ( бывает же такое..) - 100 заключенных. Все имеют пожизненный срок. Начальник тюрьмы сообщает им, что через час всех разведут в одиночные камеры и они больше никогда не увидятся и не смогут общаться. Ежедневно компьютер будет выбирать случайным образом несколько(иногда 0 выбирает компьютер) заключенных. Их по очереди будут выводить из камеры в комнату. В ней ничего нет, кроме лампочки и выключателя, которым заключенный может пользоваться (лампочку не трогать).Начальное состояние лампочки: выключенна.Любой из заключенных, в определенный момент времени может сказать, что в этой комнате побывали ВСЕ! ( не важно, по разу или несколько раз) заключенные. Если он прав- то всех отпускают. Нет- казнят. У заключенных есть час на выработку алгоритма спасения.

Как освободить заключенных???


Как любой может сказать, что все побывали, имея данные лишь включена лампа или нет...

Бред...

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

 

[talex]

Ок, тогда назовите до скольки должен считать счетчик, другими словами когда он может сказать, что все заключенные уже побывали? Пусть заключенных будет, как в оригинальном условии 17.

До 17 )))) (+1 как я писал выше для верности )

 

[talex]

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

Читаем внимательно условия "компьютер случайным образом выбирает несколько", без наличия человека-счетчика, как в предыдущей задаче - это не реально

 

[talex]

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

 

[borisd]

Читаем внимательно условия "компьютер случайным образом выбирает несколько", без наличия человека-счетчика, как в предыдущей задаче - это не реально

Внимательно прочитал условие...

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

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

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

 

[borisd]

До 17 )))) (+1 как я писал выше для верности )

Наверное, Вы оговорились и хотели написать до 16, т.к. заключенных которые могут включить А, ослаось 17 - один счетчик = 16 и (+1 как вы написали выше для верности).

Хорошо, итак, предположим, что А-вкл. это знак того,что заключенный был в камере, тогда


существует четыре возможности развития событий в начале

1.а) первым зашел обычный зек и А=выкл
1.б) первым зашел обычный зек и А=вкл
2.а) первым зашел счетчик и А=выкл
2.б) первым зашел счетчик и А=вкл

Счетчик считая до 16 в случае
1.а)считает верно и всех отпускают
1.б)считает неверно, если за все время побывали в камере все кроме одного зека
2.а)считает верно и всех отпускают
2.б)считает неверно, если за все время побывали в камере все кроме одного зека

Счетчик считая до 16 и используя +1 (для верности) в случае
1.а)вечно ждет 17-ое нажатие
1.б)считает верно
2.а)вечно ждет 17-ое нажатие
2.б)считает верно

Как Вы думаете, этот метод удовлетворяет условию задачи требующему выработать стратегию, позволяющую НАВЕРНЯКА освободиться?

 

[talex]

Насчет "вечно ждет", то в условии сказано: "считая, что они будут жить достаточно долго, чтобы побывать в этой комнате как угодно много раз каждый. "
То есть лимита по времени нет.

Насчет +1 для верности, как раз для условия неизвестности в начальном положении вкл или выкл (т.е. первый по счету, как бы пропускается). И тогда получается наверняка. Т.е. если при первом своем посещении (при условии что счетчик считает только положения вкл) он незнает включил это зэк или так и было изначально, поэтому отсчет начинается, посути, после первого посещения счетчиком комнаты, когда он сбрасывает в полож выкл.

 

[borisd]

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

Ваше решение, в некоторрых случаях, противоречит условию НАВЕРНЯКА освободится. Именно поэтому заключенные вместо одного раза должны включить выключатель по 2 раза. Это позволит им именно НАВЕРНЯКА освободится в не зависимости от начального положения выключателей и порядка заходов в камеру.

З.Ы. Я предлагаю прекратить флуд в этой ветке, т.к. правильное решение было найдено, Вас же переубеждать никто целью не ставит.

 

[Expert]

Альтернативный вариант: все расчитываются по порядку и заходя в комнату пишут (ногтем, кровью, га..ном или еще чем..) свой номер, когда ряд из чисел заполнен знач все ок. А выключатели можно просто поклацать

 

[DorFF]

Начальное условие - выключатель А в положении ВЫКЛ.

Например, кто приходит в камеру первый раз включает выкл А (если он выключен). Если в камере он уже был, либо выключатель А включен, то дергает выключатель Б.

Счетчик, видя что выкл А включен, выключает его (и начинает считать), если выключен, то дергает выключатель Б.

И того, когда счетчик 16 раз выключит выключатель А - все 17 побывали в камере.

Но тут возникает запарка, если вначале выкл А стоит включенный, то 16-й раз он его выключет, когда последний его еще не щелкнул. Т.е. есть шанс не дождацца одного чела, которого заведут в камеру.

 

[Евгений]

народ, мне кажется, что вобще не должно быть счетчика-зека, ведь его могут в эту камнату пустить только один раз. А нам нужно чтоб решение задачи было НАВЕРНЯКА, т.е. любой зашедший в комнату может понять что уже все 17 зеков здесь побывали. хм...