Здравствуйте, Gaperton, Вы писали:
G>Может уже было, не знаю. Но мне понравилось.
G>В тюрьме 100 камер-одиночек, в них сидят зэки.
G>Есть одна пустая комната, в которой есть лампа с кнопкой выключателем. Нажатие переводит лампу из состояния включено в выключено, и наоборот.
G>Есть охранник, который случайно выбирает зэка, и ведет его в комнату, где зэк может нажать, или не нажать кнопку. Охранник занимается этим постоянно, так что все зэки посетят комнату неограниченное число раз.
G>Если хотя-бы один зэк скажет, что в камере побывали все 100, и не ошибется, всех отпустят. При ошибке — расстреляют. Ошибаться нельзя.
G>Зеки могут один раз перед началом эксперимента собраться, перетереть, и добазариться, как себя вести в такой непростой ситуации. После этого они не встречаются и информацией не обмениваются.
G>Как они должны договориться, чтобы всех отпустили?
Кароче, чувак, я не зек ваще, но чиста ради хорошей задачи канкретно прикину что я на месте зека. тогда бы во время базара с пацанами сказал бы: я включаю лампу, а вы — выключаете.
вообщем:
если захожу я — включаю лампу (если она выключена).
если заходит пацан не выклюавший лампу — он её выключает.
если заходит пацан уже выклюавший лампу — он ничего не делает.
таким образом, когда я замечу что лампа выключалась 99 раз (благодяря каждому из пацанов) могу спокойно провозглашать победу
Есть одна пустая комната, в которой есть лампа с кнопкой выключателем. Нажатие переводит лампу из состояния включено в выключено, и наоборот.
Есть охранник, который случайно выбирает зэка, и ведет его в комнату, где зэк может нажать, или не нажать кнопку. Охранник занимается этим постоянно, так что все зэки посетят комнату неограниченное число раз.
Если хотя-бы один зэк скажет, что в камере побывали все 100, и не ошибется, всех отпустят. При ошибке — расстреляют. Ошибаться нельзя.
Зеки могут один раз перед началом эксперимента собраться, перетереть, и добазариться, как себя вести в такой непростой ситуации. После этого они не встречаются и информацией не обмениваются.
Как они должны договориться, чтобы всех отпустили?
Здравствуйте, hemmul, Вы писали:
H>Здравствуйте, 0x64Rm, Вы писали:
R>>Но такого в условии нет. И потому нужны скрытые дополнительные информационные записи (на стене, на лампе... H>... на охраннике
В комнату заходит пахан, выкручивает лампочку, и разбивает ее на 99 осколков, которые кладет слева от двери.
Каждый пацан, впервые побывавший в комнате, перекладывает один осколок направо от двери.
Пахан проверяет наличие кучки слева, и если она пуста, говорит: эй, начальник! Все здесь были, блябуду!
H>>Кароче, чувак, я не зек ваще, но чиста ради хорошей задачи канкретно прикину что я на месте зека. тогда бы во время базара с пацанами сказал бы: я включаю лампу, а вы — выключаете. H>>вообщем: H>>если захожу я — включаю лампу (если она выключена). H>>если заходит пацан не выклюавший лампу — он её выключает. H>>если заходит пацан уже выклюавший лампу — он ничего не делает.
H>>таким образом, когда я замечу что лампа выключалась 99 раз (благодяря каждому из пацанов) могу спокойно провозглашать победу
RB>Ну да. Если чувак 99 раз включает лампу, то это значит, что ее 99 раз выключали, причем, разные люди. RB>Но при этом вроде как предполагается, что в исходном состоянии лампа включена.
RB>А если она изначально выключена? Как бы не ошибиться на единицу...
Патч на неизвестное первоначальное состояние лампы:
если захожу я — включаю лампу (если она выключена).
если заходит пацан не выключавший лампу — он её выключает.
если заходит пацан один раз выключавший лампу — он её выключает.
если заходит пацан два раза выключавший лампу — он ничего не делает.
Здравствуйте, J-peg, Вы писали:
S>>наводящий вопрос: как можно заметить, сколько раз выключалась лампа, если кроме тебя ее никто не включает?
JP>Собственно, у меня близкий вопрос. В условии не давалось условие — могут ли уголовники видеть из своей камеры как включается/выключается лампочка. Если они не могут этого видеть, а значит, не могут сосчитать, то, видимо, решение задачи оказывается невозможным.
собственно, у меня близкий ответ... Предположим, у тебя есть комната (забудем про тюрьму). К тебе иногда заходит брательник, сестра, мать и отец, которые слушаются тебя беспрекословно. Они обязательно заходят по одному и никогда не заходят, когда ты дома. Ты любишь с друзьями попить пивка в своей комнате. После пьянки в комнате, естессно, бардак. Так вот допустим тебя осенило и ты решил, чтобы каждый из твоих родичей убрался в комнате по одному разу. Ты им так и говоришь: "Каждый зашедший в комнату должен убраться, если там грязно и если он еще не убирался там, начиная с сегодняшнего дня! В противном случае убираться запрещаю!" Ну вот теперь ответь на такой вопрос: "После какой по числу уборки ты будешь уверен, что заходили все твои родичи, если никто, кроме тебя, в комнате свинячить не имеет права, а ты не любишь убираться?"
... << Rsdn@Home 1.1.4 beta 1 >> В winamp'е зажигает Red Hot Chilli Peppers — Scar Tissue.
Здравствуйте, yeti, Вы писали:
Y>если захожу я — включаю лампу (если она выключена). Y>если заходит пацан не выклюавший лампу — он её выключает. Y>если заходит пацан уже выклюавший лампу — он ничего не делает.
Здравствуйте, Satrapp, Вы писали:
S>Здравствуйте, yeti, Вы писали:
Y>>если захожу я — включаю лампу (если она выключена). Y>>если заходит пацан не выклюавший лампу — он её выключает. Y>>если заходит пацан уже выклюавший лампу — он ничего не делает.
S>Базару нет Волки позорные совсем мозгов лишили
всё по чесноку. базара нет ту уж меня тоже звиняй — я может в первом посте поторопился — не совсем понятно выразился... но всё по понятиям... волков этих я профильтровал — вместе будем давить
Все бы хорошо, еслибы велся учет входивших в комнату человек.
Т.е. пока все люди в произвольном порядке один раз не побывают в комнате никто второй раз туда не попадет.
Но такого в условии нет. И потому нужны скрытые дополнительные информационные записи (на стене, на лампе... т.е. в комнате потому как только там все участики точно окажутся).
В случае же если учет ведется не имеет значения в каком положении находится выключатель.
Главное его вообще не трогать.
При этом все из учавствовавших это состояние (ОН-ОФФ) видели и запомнили. (инициализация)
Первый вошедший дважды и увидев что лампа находится в томже состоянии
заявляет свои права на освобождение.
Если ему говорят что он ошибся — просит показать логи вхождений в комнату.
При нарушении правил (ошибка ведения логов) заявляет свои права на амнистию.
Здравствуйте, hemmul, Вы писали:
G>>Есть охранник, который случайно выбирает зэка, и ведет его в комнату, где зэк может нажать, или не нажать кнопку. Охранник занимается этим постоянно, так что все зэки посетят комнату неограниченное число раз.
H>таким образом, когда я замечу что лампа выключалась 99 раз (благодяря каждому из пацанов) могу спокойно провозглашать победу
Нууу, брателло, я с тобой реально не согласен! А если охранник окажется редиской и реально чиста случайно будет выбирать меня, моего кореша и тебя через раз? Мне чиста не впадлу, конечно, я как реальный пацан вырублю лампу; кореша, не вопрос, тоже на это подобью — будет вырубать . Но ты прикинь, когда мы с корешем по 50 раз ее вырубим, а ты ее, в натуре, 100 раз врубишь, это же какое рубилово по всей тюрьме пойдет!
Здравствуйте, Satrapp, Вы писали: S>когда мы с корешем по 50 раз ее вырубим, а ты ее, в натуре, 100 раз врубишь, это же какое рубилово по всей тюрьме пойдет!
если захожу я — включаю лампу (если она выключена).
если заходит пацан не выклюавший лампу — он её выключает. если заходит пацан уже выклюавший лампу — он ничего не делает.
Здравствуйте, hemmul, Вы писали:
H>Кароче, чувак, я не зек ваще, но чиста ради хорошей задачи канкретно прикину что я на месте зека. тогда бы во время базара с пацанами сказал бы: я включаю лампу, а вы — выключаете. H>вообщем: H>если захожу я — включаю лампу (если она выключена). H>если заходит пацан не выклюавший лампу — он её выключает. H>если заходит пацан уже выклюавший лампу — он ничего не делает.
H>таким образом, когда я замечу что лампа выключалась 99 раз (благодяря каждому из пацанов) могу спокойно провозглашать победу
брателло, звиняй, в предыдущем посте стормозил
а так — базару нет
H>Кароче, чувак, я не зек ваще, но чиста ради хорошей задачи канкретно прикину что я на месте зека. тогда бы во время базара с пацанами сказал бы: я включаю лампу, а вы — выключаете. H>вообщем: H>если захожу я — включаю лампу (если она выключена). H>если заходит пацан не выклюавший лампу — он её выключает. H>если заходит пацан уже выклюавший лампу — он ничего не делает.
H>таким образом, когда я замечу что лампа выключалась 99 раз (благодяря каждому из пацанов) могу спокойно провозглашать победу
Ну да. Если чувак 99 раз включает лампу, то это значит, что ее 99 раз выключали, причем, разные люди.
Но при этом вроде как предполагается, что в исходном состоянии лампа включена.
А если она изначально выключена? Как бы не ошибиться на единицу...
H>>вообщем: H>>если захожу я — включаю лампу (если она выключена). H>>если заходит пацан не выклюавший лампу — он её выключает. H>>если заходит пацан уже выклюавший лампу — он ничего не делает.
RB>Ну да. Если чувак 99 раз включает лампу, то это значит, что ее 99 раз выключали, причем, разные люди. RB>Но при этом вроде как предполагается, что в исходном состоянии лампа включена. RB>А если она изначально выключена? Как бы не ошибиться на единицу...
ну вроде как те, которые зайдут в комнату до первого захода "включателя", не выключают лампу. Поэтому они должны будут потом ее выключить. Когда "включатель" первый раз включает лампу, он вроде как "не замечает", что ее уже выключали и поэтому это "нищитаицца"
Здравствуйте, rus blood, Вы писали:
H>>таким образом, когда я замечу что лампа выключалась 99 раз (благодяря каждому из пацанов) могу спокойно провозглашать победу
RB>Ну да. Если чувак 99 раз включает лампу, то это значит, что ее 99 раз выключали, причем, разные люди. RB>Но при этом вроде как предполагается, что в исходном состоянии лампа включена.
RB>А если она изначально выключена? Как бы не ошибиться на единицу...
да, ты прав — я не знаю начальное состояние лампы. поэтому-то я и считаю выключения последовавшие после моих включений — если их 99 — то всего выключений может быть 100 (в случае если лампа до меня включена)
Здравствуйте, hemmul, Вы писали:
H>Здравствуйте, rus blood, Вы писали:
H>>>таким образом, когда я замечу что лампа выключалась 99 раз (благодяря каждому из пацанов) могу спокойно провозглашать победу
RB>>Ну да. Если чувак 99 раз включает лампу, то это значит, что ее 99 раз выключали, причем, разные люди. RB>>Но при этом вроде как предполагается, что в исходном состоянии лампа включена.
RB>>А если она изначально выключена? Как бы не ошибиться на единицу...
H>да, ты прав — я не знаю начальное состояние лампы. поэтому-то я и считаю выключения последовавшие после моих включений — если их 99 — то всего выключений может быть 100 (в случае если лампа до меня включена)
ой ой сорри — правильно — тогда одного пацана "теряем"
тогда уж лучше применить патчи Tan4ik-а — тише едешь дальше будешь
Здравствуйте, 0x64Rm, Вы писали:
R>Но такого в условии нет. И потому нужны скрытые дополнительные информационные записи (на стене, на лампе...
... на охраннике
Здравствуйте, Satrapp, Вы писали:
S>Здравствуйте, nogtol, Вы писали:
N>>чего то я не пойму, а как можно заметить сколько раз выключалась лампа?
S>наводящий вопрос: как можно заметить, сколько раз выключалась лампа, если кроме тебя ее никто не включает?
Собственно, у меня близкий вопрос. В условии не давалось условие — могут ли уголовники видеть из своей камеры как включается/выключается лампочка. Если они не могут этого видеть, а значит, не могут сосчитать, то, видимо, решение задачи оказывается невозможным.
Здравствуйте, Gaperton, Вы писали:
G>В тюрьме 100 камер-одиночек, в них сидят зэки... G>Как они должны договориться, чтобы всех отпустили?
Хочу проанализировать первое (и по сути единственое) решение.
Итак, допустим охранник водит в день 10 человек к этой самой зветной комнате.
В среднем всех людей он может в лучшем случае отвести за 10 дней, а в худшем — никогда
Но все же возмем коэффициент запаса = 2. В итоге всех отведет за 20 дней. Т.е. реально за месяц
все могут быть свободны, но при условии что вначале смогут решить эту задачу.
А теперь ваш ответ, следуя аналогичным рассуждениям "пахана" 100 раз отведут в комнату только через
100*2=200 дней. Я думаю, что такой результат никого бы не устроил. Нужно рыть дальше.
Все — а сейчас я буду думать над решением, если надумаю — отвечу в следующем посте.
Re[2]: Тюрьма
От:
Аноним
Дата:
19.08.04 22:44
Оценка:
P>Все — а сейчас я буду думать над решением, если надумаю — отвечу в следующем посте.
Т.к. из условия не ясно видно ли из камер состояние лампочки, то будем решать разные варианты:
Итак вариант когда ламочка видна отвсюду простой, его решение следующее:
если лампочка включена, то все ее выключают
если лампочка включена, то:
-если человек не включал лампочку — он включает
-если человек уже включал лампочку — он ничего не делает
В итоге как только последний человек войдет первый раз в камеру * 1.5 (коллизии на уже включенную лампочку) —
мы сразу это заметим. Следовательно все выйдут ровно через месяц...
Для варианта когда лампочка не видна все сложнее — буду думать...
P>>Все — а сейчас я буду думать над решением, если надумаю — отвечу в следующем посте.
Кстати уточнение к моей оценки ваших решений, время, которое потребуется для решения вашего варианта равно не 200 дней, а 2000:
т.е. 100*100*2 / 10 итераций в день... Вот такие пироги поэтому нужно искать более лучшие решения.
А>Для варианта когда лампочка не видна все сложнее — буду думать...
Есть неточное решение, зависящее от свойств генератора случайных чисел охранника
Алгоритм таков:
Когда человек первый раз входит в комнату — он инвертирует состояние лампочки
В остальных случаях он ничего не делает, а только запоминает информацию о состоянии.
Таким образом, если состояние меняется с момента последнего посещения — значит недавно был
первый раз какой-то человек. Если стостояние не менялось подряд 10 раз, то значит никого уже
давно не было. И с высокой точностью (а степень этой точности зависит как раз от этого числа!)
можно предположить что все уже были.
Собственно нужны доп. условия. Т.к. эта задача наверняка из реальной жизни (например какого-нибудь распознавания образа и т.п.),
то всегда можно сделать допущения на точность в обмен на скорость, а значит это решение может быть лучшим.
P>Таким образом, если состояние меняется с момента последнего посещения — значит недавно был P>первый раз какой-то человек. Если стостояние не менялось подряд 10 раз, то значит никого уже P>давно не было. И с высокой точностью (а степень этой точности зависит как раз от этого числа!) P>можно предположить что все уже были.
Собственно можно уточнить это число следующим образом:
это число должно быть не меньше 10, но и не меньше 2*К, где К — количество его посещений в ситуации
когда лампочка меняла свое состояние. Таким образом выполняется некоторая калибровка генератора случ.
чисел охранника. Например на случай если он будет водить одного и того же человека через раз. В этом
случае он 100 раз заметит изменение, а потом наступит затишье...
Собственно коэффициент 2, как и число 10 взято наобум, но примерно отражают суть — точные значения нужно брать
из эксперимента.
S>чтобы каждый из твоих родичей убрался в комнате по одному разу.
А как это вообще возможно? Убраться в комнате можно только один раз, поскольку если один человек уберётся в комнате, то она станет чистой, а чистую комнату убрать в дальнейшем невозможно. Следовательно, больше никто не сможет убрать мою комнату. Следовательно, все родители убраться в моей комнате не могут.
S> Ну вот теперь ответь на такой вопрос: "После какой по числу уборки ты будешь уверен, что заходили все твои родичи, если никто, кроме тебя, в комнате свинячить не имеет права, а ты не любишь убираться?"
Даже если предположить что одну комнату можно убрать несколько раз или же я каждый день там свинячу, я никогда не буду уверен что в комнате побывали все мои родичи. Отец мог всё время проваляться на диване и не двигаться, а мать часто заходить в мою комнату и постоянно там убираться. Или я неправ?
P>>Таким образом, если состояние меняется с момента последнего посещения — значит недавно был P>>первый раз какой-то человек. Если стостояние не менялось подряд 10 раз, то значит никого уже P>>давно не было. И с высокой точностью (а степень этой точности зависит как раз от этого числа!) P>>можно предположить что все уже были. P>Собственно можно уточнить это число следующим образом: P>это число должно быть не меньше 10, но и не меньше 2*К, где К — количество его посещений в ситуации P>когда лампочка меняла свое состояние. Таким образом выполняется некоторая калибровка генератора случ. P>чисел охранника. Например на случай если он будет водить одного и того же человека через раз. В этом P>случае он 100 раз заметит изменение, а потом наступит затишье...
P>Собственно коэффициент 2, как и число 10 взято наобум, но примерно отражают суть — точные значения нужно брать P>из эксперимента.
Загвоздка ещё в том, что один из заключённых может за это время:
а) умереть;
б) быть освобождён;
в) заболеть заразной болезнью.
Таким образом, со временем, с увеличением вероятности прохода всех заключённых через эту комнату, увеличивается также вероятность исключения заключённого из эксперимента, а значит, сведения задачи к нерешаемой, поскольку по условию задачи, один из зэков должен сказать что все 100 прошли через эту комнату. Если из эксперимента выбыл тот участник, что в комнате не был, задача становится нерешаемой. Другими словами, увеличение шансов на победу со временем компенсируется уменьшением шансов успешной комбинации так таковой.
Третий случай — пример отношения тюремщика к заключённому. Если тюремщик боится выпускать зэка их камеры или боится к нему подойти, то маловероятно что через комнату пройдут все зэки.
JP>А как это вообще возможно? Убраться в комнате можно только один раз, поскольку если один человек уберётся в комнате, то она станет чистой, а чистую комнату убрать в дальнейшем невозможно. Следовательно, больше никто не сможет убрать мою комнату. Следовательно, все родители убраться в моей комнате не могут.
JP>Даже если предположить что одну комнату можно убрать несколько раз или же я каждый день там свинячу, я никогда не буду уверен что в комнате побывали все мои родичи. Отец мог всё время проваляться на диване и не двигаться, а мать часто заходить в мою комнату и постоянно там убираться. Или я неправ?
... Ты им так и говоришь: "Каждый зашедший в комнату должен убраться, если там грязно и если он еще не убирался там, начиная с сегодняшнего дня! В противном случае убираться запрещаю!" ...
т.е.
if ((грязно)&&(не убирался)) { уберись }
else { свободен };
... << Rsdn@Home 1.1.4 beta 1 >> В winamp'е зажигает Woman From Tokyo
JP>Так бы сразу и сказал. Только мне всё равно неясно: после какого раза я могу уверенно сказать что в моей комнате перебывали все?
ТОчнее, не так. В случае с комнатой всё очевидно. Я — единственный кто знает сколько раз я там насвинячил и единственный кто веду статистику уборок. ПОэтому достаточно насвинячить ровно столько раз сколько членов остальной семьи в доме. В случае же с тюрмой, статистику посещений ведёт только надзиратель. Никто из зэков не знает сколько раз в комнате перебывало народу и не знает сколько раз была включена/выключена лампочка. Вот в чём дело.
Здравствуйте, J-peg, Вы писали:
JP>>Так бы сразу и сказал. Только мне всё равно неясно: после какого раза я могу уверенно сказать что в моей комнате перебывали все?
JP>ТОчнее, не так. В случае с комнатой всё очевидно. Я — единственный кто знает сколько раз я там насвинячил и единственный кто веду статистику уборок. ПОэтому достаточно насвинячить ровно столько раз сколько членов остальной семьи в доме. В случае же с тюрмой, статистику посещений ведёт только надзиратель. Никто из зэков не знает сколько раз в комнате перебывало народу и не знает сколько раз была включена/выключена лампочка. Вот в чём дело.
в случае с тюрьмой известно, сколько раз включалась лампочка, поскольку кроме тебя там никто свет не включает (так же как в случае с комнатой никто не свинячит, кроме тебя).
... << Rsdn@Home 1.1.4 beta 1 >> В winamp'е зажигает Woman From Tokyo
S>в случае с тюрьмой известно, сколько раз включалась лампочка, поскольку кроме тебя там никто свет не включает (так же как в случае с комнатой никто не свинячит, кроме тебя).
Да, теперь я понял. Выбирается один человек, кто включает лампочку. Остальные её выключают если они ещё этого не делали. Отсюда выходит ещё одно "но". 99 заключённых должны побывать в комнате хотя бы один раз. Один заключённый должен побывать там не менее 99 раз.
Волки позорные совсем мозгов лишили 
