Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 252
Начальники развлекаются, придумали себе забаву…
элементарно, каждый из заключённых отмечает каждый прожитый день. кто пойдёт на 100 день в ту камеру, говорит «да» и все радуются и смеются при этом убегая в тундру =)
P.S. и не говорите мне что это не по заданию, там нет никаких ограничений на такие действия. никто же не сказал, что обязательно использовать эту лампочку — обычно в логических задачах некоторые элементы условия призваны просто запутать решающего.
P.S. и не говорите мне что это не по заданию, там нет никаких ограничений на такие действия. никто же не сказал, что обязательно использовать эту лампочку — обычно в логических задачах некоторые элементы условия призваны просто запутать решающего.
ой-ой-ой с колбасой! «вразброс и с повторениями». Я как тюремщик могу вызывать первые 50 дней первого зека, а вторые 50 дне — второго.
вот, блин, опозорился из-за невнимательности. извиняюсь.
Зеки договариваются между собой, что оставляют лампочку зажженной только если он здесь был первый раз. Следующий зек, который видит, что лампочка зажжена, гасит ее и считает сколько раз он ее погасил. Если зек пришел, а лампочка не горит и он тут уже был и у него есть счетчик погашенных лампочек (лампочек, которые он погасил), он зажигает лампочку и уменьшает свой счетчик. Тот кто первый наберет 100 на своем счетчике тот и скажет, что все ок.
можно немного улучшить алгоритм, если добавить условие:
если зек тут уже был, но вчера тут не был и позавчера тут не был и лампочка горит, то лампочку он считает, но не выключает (передавая счетчик следующему зеку, который руководствуется тем же правилом.
если зек тут уже был, но вчера тут не был и позавчера тут не был и лампочка горит, то лампочку он считает, но не выключает (передавая счетчик следующему зеку, который руководствуется тем же правилом.
отлично, это второе алгоритмическое решение! Премия и почести!
сейчас написал программу и понял что это слишком долго, мое решение ниже лучше.
полное решение задачи на PHP s-c.me/Mi (где-то через 60000 дней они выйдут)
Хммм… 164 года… интересно это учитано в задаче?
еще как! Бессмертность и эльфичность зэков позволяет им быть неторопливыми
немного подумав, уменьшил среднее время в заключении в два раза, добавив такое условие:
Если один зек уже знает, что другой зек тут был, но лампочка в период этого зека не горит, то этот зек сам включает лампочку, чтобы сказать об этом тем, кто этого еще не знает. обновленный исходник: s-c.me/Ml теперь некоторые зеки выйдут даже если они будут не бессмертны!
Если один зек уже знает, что другой зек тут был, но лампочка в период этого зека не горит, то этот зек сам включает лампочку, чтобы сказать об этом тем, кто этого еще не знает. обновленный исходник: s-c.me/Ml теперь некоторые зеки выйдут даже если они будут не бессмертны!
Вот это habrahabr.ru/blogs/zadachki/69558/#comment_1983053 решение с периодом 100 дней сокращает время заключение до «приемлимых» 80 лет.
решил всетаки запрограммировать, то что я тут написал, и понял что слишком долго зеки будут выходить. Думаю стоит распространить информацию между как можно большим количеством зеков, т.е. договорится что есть так называемый период распостранения информации. т.е. каждый зек, может разговаривать только в свой отрезок, скажем 100 дней, остальные в этот отрезок не должны ничего делать, а просто смотреть на лампочку, зная что если в этом отрезке она горит, то это зек номер N ее включил, так как там был итого нужно около 100*Period дней чтобы хотябы один зек увидел все лампочки от всех зеков.
да, забыл сказать каждый 100й день есть день так называемого сброса информации, зек который приходит в этот день выключает лампочку полюбому. Если 100*Period дней не хватит, то все повторяется.
Это было лимитное решение!!! В пределе получается, что они выйдут. Поздравляю. Остались только очень злокозненные варианты.
Кстати, когда я додумался до этого решения, я не смог оптимизировать период. Есть идеи?
Кстати, когда я додумался до этого решения, я не смог оптимизировать период. Есть идеи?
Допустим, мы водим двух зеков.
1. Зек №1 — вкл
2. Зек №2 — вкл
3. Зек №1 — выкл
4. Зек №2 — вкл
5. Зек №1 — выкл
…
20х (лень считать). Зек №1/2 — расстрел.
1. Зек №1 — вкл
2. Зек №2 — вкл
3. Зек №1 — выкл
4. Зек №2 — вкл
5. Зек №1 — выкл
…
20х (лень считать). Зек №1/2 — расстрел.
или я чего-то не понимаю, или тут используется сильно больше одного бита памяти :)
Если считать, что лампочка видна остальным заключенным, решение такое: все, кто был в камере первый раз включают лампочку, если того же заключенного ведут во второй раз — выключают. Соотв-но, если в общей сложности лампочка будет гореть 100 дней, все заключенные побывали в камере, можно говорить «да» :)
Лампочка тут видимо не спроста =)
Да было это уже на хабре. trueClearThinker написал правильно. Единственное, что он не упомянул — назначить одного человека «счётчиком» горящих лампочек, которые после 99 раз говорит «да».
Есть решение со счетчиком, но это не решение trueClearThinker. Вот глядите:
Пусть счетчик — зэк номер 0100.
Изначально лампа выкл.
1-й день — заходит зэк 0001. Лампа вкл
2-й день — заходит зэк 0001. Лампа выкл
3-й день — заходит зэк 0002. Лампа вкл
4-й день заходит зэк 0100. Видит включенную лампу. Что он посчитает, увидев вкл. лампу? Что один чувак был тут впервые. И все.
Пусть счетчик — зэк номер 0100.
Изначально лампа выкл.
1-й день — заходит зэк 0001. Лампа вкл
2-й день — заходит зэк 0001. Лампа выкл
3-й день — заходит зэк 0002. Лампа вкл
4-й день заходит зэк 0100. Видит включенную лампу. Что он посчитает, увидев вкл. лампу? Что один чувак был тут впервые. И все.
А точнее мы имхо определить не сможем, в любом случае многим придется ходить по много раз, пока счетчик все не посчитает правильно. Но это лучше чем расстрел :)
2 день — неверно.
Зэк включает лампу только если она выключена и только если он тут первый раз.
Выключать лампу может только счётчик.
Зэк включает лампу только если она выключена и только если он тут первый раз.
Выключать лампу может только счётчик.
Это из «Архипелага ГУЛАГа» в редакции для изучения в классах с лженаукой кибернетикой?
допустим лампочка была включена:
одного зека назначают главным. он только включает лампочку и считает сколько раз он ее включил.
остальные зеки если приходят в первый раз — выключают лампочку. если втрой и более — ничего не трогают.
как только главный зек насчитает 100 — он и скажет что все побывали в этой комнате.
одного зека назначают главным. он только включает лампочку и считает сколько раз он ее включил.
остальные зеки если приходят в первый раз — выключают лампочку. если втрой и более — ничего не трогают.
как только главный зек насчитает 100 — он и скажет что все побывали в этой комнате.
да, отличное решение! Сможете оценить вероятность выхода?
Есть еще парочка решений. Одно основано на разбиении вечности на промежутки, найдете?
Есть еще парочка решений. Одно основано на разбиении вечности на промежутки, найдете?
вероятность 0,01-что выберут конкретного из кучи
вероятность выхода 0,0001 получается.
но тут еще вероятность должна зависеть от того, что главного зека выберут. и он сможет увидеть состояние лампочки. но я не знаю как… не могу вспомнить теорию вероятности.
но вероятность выхода будет намного меньше чем 0,0001, скажем 0,0001/100=0,000001 или вроде того.
вероятность выхода 0,0001 получается.
но тут еще вероятность должна зависеть от того, что главного зека выберут. и он сможет увидеть состояние лампочки. но я не знаю как… не могу вспомнить теорию вероятности.
но вероятность выхода будет намного меньше чем 0,0001, скажем 0,0001/100=0,000001 или вроде того.
Главным будет тот, кого первым введут.
вероятность выхода 1 т.к. время не ограничено.
я имел в виду вероятность выхода по прошествии 100 дней.
а я имел ввиду, разумеется, оценку времени выхода, а не вероятность
У меня оценка почти в 30 лет получилась: пост
Пожалуй присоединюсь к рассуждениям, первое что пришло в голову) В предложенном решении после считывания информации счётчик может либо увеличиться на единицу, либо остаться без изменений.
Если предположить, что поначалу чаще будут заходить зеки, которые ещё не были в комнате, то можно немного оптимизировать процесс. Например, разобьём дни на группы по четыре, пусть это будут старшие биты послания зеку-счётчику — 00, 01, 10, 11. Младший бит — состояние лампочки (вкл / выкл). Соответственно, когда младший бит == 0, счётчик не меняется, иначе счётчик += 1, за исключением случая когда послание == 111, тогда счётчик += 2. Правда в таком случае если послание == 110, может потеряться информация, но в нашем предположении этот случай менее вероятен, чем 111. По-моему это должно немного ускорить процесс освобождения, насколько конкретно — надо считать. Ну и ещё нужно оценить границы применимости этого предположения, то есть через сколько дней переходить на обычную систему подсчёта. Надеюсь, доступно изложил)
Если предположить, что поначалу чаще будут заходить зеки, которые ещё не были в комнате, то можно немного оптимизировать процесс. Например, разобьём дни на группы по четыре, пусть это будут старшие биты послания зеку-счётчику — 00, 01, 10, 11. Младший бит — состояние лампочки (вкл / выкл). Соответственно, когда младший бит == 0, счётчик не меняется, иначе счётчик += 1, за исключением случая когда послание == 111, тогда счётчик += 2. Правда в таком случае если послание == 110, может потеряться информация, но в нашем предположении этот случай менее вероятен, чем 111. По-моему это должно немного ускорить процесс освобождения, насколько конкретно — надо считать. Ну и ещё нужно оценить границы применимости этого предположения, то есть через сколько дней переходить на обычную систему подсчёта. Надеюсь, доступно изложил)
забыл добавить, что включать лампочку может тока главный зек. другие если лампочка выключена ее не трогают.
Очень не эффективный метод получается. Если считать что всех зеков заводят по порядку или в случайном порядке, счетчик будет попадать в комнату 100 раз. Это 10 000 дней, т.е. 30 лет, у многих срок и так кончиться, другие умрут.
откровенно говоря, это самый быстрый вариант, который я лично смог найти.
> у многих срок и так кончиться, другие умрут.
а это уже совсем другая история ©
а это уже совсем другая история ©
а ещё этот способ ломается если посреди эксперимента кто-нибудь умирает — если умрёт человек, ни разу не побывавший в комнате, то все так и будут сидеть ждать.
1-го сентября 100 бессмертных эльфийских воркутинских зэков постоили на торжественную линейку
habrahabr.ru/blogs/zadachki/69558/#comment_1981932:
Ок?
поправил условие — даровал зэкам бесконечную жизнь.
Ок?
Но в этом решении ответственный «пахан» должен заходить строго за зеком! за одним зеком! а если между приходами пахана прошли 5 зеков? только первый сделает явное действие, и никто из последующих не включит и не выключит лампочку (как они выключат ее, если она уже выключена?), а они-то ведь уже побывали в камере… четверо значит останутся неучтенными?
А если «главного» запустят в камеру всего один раз?
А если главный зэк всего один раз побывает в камере? Как он сможет посчитать?
В блоге «занимательные задачки» была похожая задача. И, да, очень символична аналогия: зеки, 1 сентября, торжественная линейка… автор в школьные годы чувствовал себя как в тюрьме?
Как-бы боян, ну и Devgru, упомянув про счетчика, фактически открыл всю соль задачи :)
единственный минус такого решения… этот один зек может умереть раньше чем в 100 раз увидит горящую лампочку…
Каждый зек при первом попадании в камеру включает лампочку, если та была выключена (кстати, в задаче не сказано, что включать/выключать могут только зеки) :), затем надкусывает палец или губу и оставляет на стене пятно крови. Если видит рядом еще 99 пятен — зовет начальника и на свободу с чистой совестью :)
каждый зек попадая первый раз в комнату ставит себе на лбу ожог лампочкой. После 1-го сентября после и после проверки что у всех есть ожог, первый заходящий зек говорит да.
Хм… Обычный двоичный семафор. К чему зэки и всякие воркутинские обвязки? Один процесс считает сигнальные события, другие ему сигналят однократно. И всё.
Самое простое решение на день № 100^100-1 включить лампу, а на следующий сказать Да и все =) Или просто в последний день сказать Да.
1) когда зек заходит впервые и лампочка Не горит — он её включает, если горит, то зек считает что он и не заходил и ждёт положения когда он войдет при выключенной лампочке.
2) подсчет включенных лапочек и их выключение производится счетчиком. он должен 99 раз выключить лампочку. и он же говорит «да», когда попадет к лампочке вновь.
2) подсчет включенных лапочек и их выключение производится счетчиком. он должен 99 раз выключить лампочку. и он же говорит «да», когда попадет к лампочке вновь.
Да, вы нашли аглоритмическое решение задачи и будет премированы! Теперь оценка времени.
И найдите же кто-нибудь другие решения!!!
И найдите же кто-нибудь другие решения!!!
Пусть n — число зеков.
Возьмем P(A) как вероятность входа зека (не счетчика!) впервые. Она измеряется в пределах от n-1/n до 1/n, т.е. n-i/n, где i — число еще не входивших зеков.
Возьмем P(B) как вероятность входа счетчика. Она постоянна и равна 1/n.
Общая вероятность наступления терминального условия (когда все пройдут и поиздеваются над переключателем и нитью накала) — сумма по всем i от 1 до n-1 значений: P(A)+P(B).
Тогда среднее время для данных величин (L) величина обратная значениям:
L(A) = n/(n-i), L(B) = n.
Тогда общее время — сумма сумм :)
L = summ[ n-1… 1 ]( n/(n-i) + n ) = sum( n/( n-i ) ) +n(n-1)
сумма ряда вида 1/(n-1) + 1/(n-2)… + 1, если мне память не изменяет, равна logen, т.е. ln(n). получаю:
n * ln(n) + n2 — n
а это где-то порядка 10360,517… дней. ~345 месяца ~28.77 лет
Возьмем P(A) как вероятность входа зека (не счетчика!) впервые. Она измеряется в пределах от n-1/n до 1/n, т.е. n-i/n, где i — число еще не входивших зеков.
Возьмем P(B) как вероятность входа счетчика. Она постоянна и равна 1/n.
Общая вероятность наступления терминального условия (когда все пройдут и поиздеваются над переключателем и нитью накала) — сумма по всем i от 1 до n-1 значений: P(A)+P(B).
Тогда среднее время для данных величин (L) величина обратная значениям:
L(A) = n/(n-i), L(B) = n.
Тогда общее время — сумма сумм :)
L = summ[ n-1… 1 ]( n/(n-i) + n ) = sum( n/( n-i ) ) +n(n-1)
сумма ряда вида 1/(n-1) + 1/(n-2)… + 1, если мне память не изменяет, равна logen, т.е. ln(n). получаю:
n * ln(n) + n2 — n
а это где-то порядка 10360,517… дней. ~345 месяца ~28.77 лет
я думаю, что выпуск в тундру «на свободу» для зэков равносилен высшей мере… попробуй в робе протопай 100-200 км до ближайшего жилья…
Представляете, и тут, в самый ответственный момент, лампочка перегорает!
Насколько я понимаю, формально можно вычислить искомое время лишь с определенной достоверностью, скажем 99%. Ибо даже рандомный охранник может выбрать одного и того же зека 100 раз подряд с вероятностью 0,5^100 (7,8х10-31).
(Вспомнилась цитата с баша про то, как препод по терверу 5 раз бросил монетку орлом).
(Вспомнилась цитата с баша про то, как препод по терверу 5 раз бросил монетку орлом).
Так как заключенные могут договориться только 1 сентября после торжественной линейки, они просто дожидаются, как пройдет год и на торжественном обеде спрашивают друг друга кто видел лампочку, а кто нет. Если нет, то ждут следующий год.
>Есть еще предельное (lim'итное) и социальное
Первый вошедший в камеру зек должен сказать «Да». Это будет самое быстрое социальное решение.
Первый вошедший в камеру зек должен сказать «Да». Это будет самое быстрое социальное решение.
Ну почему же, еще как катит, во первых в этом случае зэки сами выбирают смерть чтобы не мучаться иллюзией надежды. Да и охраникам проще их убить. И для общества хорошо, зэков содержать не нужно.
И их всех казнят. Задача решена в кратчайшие сроки. Все условия выполнены. Ведь они покинут тюрьму. Где мой приз — поездка в Воркуту :)
Ну а если серьезно, может например зек который зашел в камеру первый раз должен снять с себя правый носок. Потом просто надо посчитать сколько носков уже лежит в камере и сделать вывод. А если ответ должен быть дан до того как он посчитает носки, то можно например первого сентября посчитать по ногам, сколько зеков без носок. и если уже все, то ответить «да».
Ну а если серьезно, может например зек который зашел в камеру первый раз должен снять с себя правый носок. Потом просто надо посчитать сколько носков уже лежит в камере и сделать вывод. А если ответ должен быть дан до того как он посчитает носки, то можно например первого сентября посчитать по ногам, сколько зеков без носок. и если уже все, то ответить «да».
ну так как зеки у нас «бессмертные эльфийские воркутинские» то можно так:
первый день первый зек включает лампочку
каждый, кто заходит первый раз лампочку не трогает
кто заходит второй раз выключает лампочку
каждый зек считает до 100
на 100й день если лампочка горит, то это означает, что все были по одному разу говорит «ДА»
если на 100ое посещение лампочка не горит, то включает и говорит «НЕТ»
все поняв, что он сказал «НЕТ» на 100 день делают вывод, что кто-то побывал в эти 100 дней там не один раз… начинаем все заново
очень неоптимально, но когда-то должно случиться, что за 100 дней каждого сводят туда по одному разу!
первый день первый зек включает лампочку
каждый, кто заходит первый раз лампочку не трогает
кто заходит второй раз выключает лампочку
каждый зек считает до 100
на 100й день если лампочка горит, то это означает, что все были по одному разу говорит «ДА»
если на 100ое посещение лампочка не горит, то включает и говорит «НЕТ»
все поняв, что он сказал «НЕТ» на 100 день делают вывод, что кто-то побывал в эти 100 дней там не один раз… начинаем все заново
очень неоптимально, но когда-то должно случиться, что за 100 дней каждого сводят туда по одному разу!
Один из преступников только выключает свет, а остальные только включают его. Преступник-выключатель подсчитывает выключения и на основании их количества делает вывод о числе «нормальных преступников» отбывших наказание.
Первого сентября на линейке зэки договариваются о том, кто из них будет главным. Потом все они (кроме главного) дружно разбивают себе головы об угол тюремной камеры.
Единственный выживший зэк может спокойно идти в комнату с лампой и сказать, что мол, да, теперь все в комнате с лампочкой побывали.
Единственный выживший зэк может спокойно идти в комнату с лампой и сказать, что мол, да, теперь все в комнате с лампочкой побывали.
На вопрос «А все ли твои товарищи тут были хотя бы раз?» можно ответить «Да, все, потому что у меня нет товарищей»
Написал на php решение чтобы точно подсчитать количество дней.
Всегда выходит между 8000 — 12000 дней.
Долго однако =). Может сделать вариант с двумя лампочками?
Всегда выходит между 8000 — 12000 дней.
Долго однако =). Может сделать вариант с двумя лампочками?
Ты забыл что можно каждые 365 дней актуализировать значение $switches (людей которые были в комнате и которых посчитал главный), увеличивая его на то число, которое главный посчитает 1ого сентября на общей линейке. Я думаю, что число упадет до 1,5-2 т. дней…
тогда это будет задачка про маркса (ссылка в начале)
Надо в эту тюрьму Майкла Скофилда посадить. Через неделю будет массовый prison break :)
2 февраля 1999 года Конституционный суд России вынес Постановление № 3-П, в котором признал неконституционным возможность вынесения смертных приговоров в отсутствие судов присяжных во всех регионах страны.
Согласно УК РФ смертная казнь в порядке помилования может быть заменена пожизненным заключением или сроком лишения свободы на 25 лет. Для отбывающих пожизненное заключение в России действует всего три специальные колонии: на острове Огненном Вологодской области, близ поселка Лозьва в Свердловской области и в Мордовии.
Мы же имеем дело с воркутинскими заключенными — значит их высшая мера — 25 лет. При алгоритмическом варианте решения этой задачи пришлось бы ждать около 30 лет. Так что сказать в первый же день нет и подождать всего:) 25 лет — гораздо более эффективный выход из данной ситуации.
Согласно УК РФ смертная казнь в порядке помилования может быть заменена пожизненным заключением или сроком лишения свободы на 25 лет. Для отбывающих пожизненное заключение в России действует всего три специальные колонии: на острове Огненном Вологодской области, близ поселка Лозьва в Свердловской области и в Мордовии.
Мы же имеем дело с воркутинскими заключенными — значит их высшая мера — 25 лет. При алгоритмическом варианте решения этой задачи пришлось бы ждать около 30 лет. Так что сказать в первый же день нет и подождать всего:) 25 лет — гораздо более эффективный выход из данной ситуации.
Бессмертным зэкам 7 лет расстрела с конфискацией :)
Есть мысля навеяная Slotted Aloha.
Считаем выключенную лампочку collision'ом.
Slot — среднестатистический промежуток времени за который все должны побывать внутри.
Начальный статус лампочки — вкл.
После первого слота если зашедший зэк в комнате впервой он выключает лампочку, до следующего слота лампочку никто не трогает. Первый кто заходит в начале следующего слота включает её. Собственно можно говорить стражнику «Да» если лампочка остаёться включенной до конца слота. Сумбурно, но думаю мысль сумел передать.
Есть мысля навеяная Slotted Aloha.
Считаем выключенную лампочку collision'ом.
Slot — среднестатистический промежуток времени за который все должны побывать внутри.
Начальный статус лампочки — вкл.
После первого слота если зашедший зэк в комнате впервой он выключает лампочку, до следующего слота лампочку никто не трогает. Первый кто заходит в начале следующего слота включает её. Собственно можно говорить стражнику «Да» если лампочка остаёться включенной до конца слота. Сумбурно, но думаю мысль сумел передать.
www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
Инженеру необязательно изобретать велосипеды. Есть задача. Инженер должен сопоставить затраты на выполнение задачи. Если эту работу проделал уже кто-либо другой и меня устраивает результат, то зачем мне тратить n-ное количество времени на то, что можно решить быстрее, воспользовавшись чьим-то трудом?
Человек задал существующую (уже известную в мире) задачу, придуманную не им. Почему я не могу воспользоваться решениями, просчитанными не мной?
Человек задал существующую (уже известную в мире) задачу, придуманную не им. Почему я не могу воспользоваться решениями, просчитанными не мной?
Заметьте, что я не стал присваивать решение себе.
Вспомните загадку «Зимой и летом одним цветом». Думаю, что вы не сами догадались, что это ель, а вам кто-то когда-то сказал. Если бы я задал такую задачку на хабре, глупо полагать, что вы бы сами думали. Вы бы ответели ответом, который вы когда-то узнали. Я поступил также. Повторюсь, что задаче в обед сто лет.
Вспомните загадку «Зимой и летом одним цветом». Думаю, что вы не сами догадались, что это ель, а вам кто-то когда-то сказал. Если бы я задал такую задачку на хабре, глупо полагать, что вы бы сами думали. Вы бы ответели ответом, который вы когда-то узнали. Я поступил также. Повторюсь, что задаче в обед сто лет.
большое спасибо за ссылку! Честно говоря, мне задачку одна девушка на работе задала. Кину ссылку на первоисточник!
Но цель-то была заставить всех поломать мозги, а не погуглить.
Но цель-то была заставить всех поломать мозги, а не погуглить.
Фундаментальный труд!
Предположим, что охранники непредвзятые и преставляют собой «классический» псевдослучайный алгоритм.
Тогда можем решить задачу эмпирическим путем — программно 100000 раз просимулировав псевдослучайный выбор в массиве из 100 элементов, и для верности взяв максимальное значение.
получась маленькая программка (на ruby), которая за 5 минут посчитала 100тыс итераций, и выдала максимальное значение = 1795 дней.
Если зэки очень хотят остаться живыми — то они могут это число и увеличить раз эдак в 100. Всё равно же бессмертные :)
этот алгоритм зэки могут выбрать если:
а) они не дружные зэки, и так и не смогли договориться кто из них главный :)
б) в какой-то момент лампочка перегорела, и, в условиях кризиса, финансирование не позволяет поставить новую :))
в) их всех устраивает <0.[..]1% вероятноcть погибнуть
Тогда можем решить задачу эмпирическим путем — программно 100000 раз просимулировав псевдослучайный выбор в массиве из 100 элементов, и для верности взяв максимальное значение.
получась маленькая программка (на ruby), которая за 5 минут посчитала 100тыс итераций, и выдала максимальное значение = 1795 дней.
Если зэки очень хотят остаться живыми — то они могут это число и увеличить раз эдак в 100. Всё равно же бессмертные :)
этот алгоритм зэки могут выбрать если:
а) они не дружные зэки, и так и не смогли договориться кто из них главный :)
б) в какой-то момент лампочка перегорела, и, в условиях кризиса, финансирование не позволяет поставить новую :))
в) их всех устраивает <0.[..]1% вероятноcть погибнуть
первый зек — включает лампочку
каждый последующий зек при заходе в камеру:
1) если он там уже был — «переключает», тоесть зажигает горящую или тушит горящую
2) если не был — свет не трогает
при этом каждый зек считает дни с 1 сентября и при входе анализирует
сколько «уникальных посещений» было в камере.
дальше пока не знаю…
каждый последующий зек при заходе в камеру:
1) если он там уже был — «переключает», тоесть зажигает горящую или тушит горящую
2) если не был — свет не трогает
при этом каждый зек считает дни с 1 сентября и при входе анализирует
сколько «уникальных посещений» было в камере.
дальше пока не знаю…
Если вероятность появления зэка в камере в любой день 1/100, то задачу можно решить так: вычислить мат. ожидание события «все зэки побывали в комнате с лампочкой» (это будет некое числи N, сейчас уже не помню, как его считать, но думаю, что-то около 1000). Зэки должны считать дни своего заключения. После наступления дня N зэки должны действовать по следующему сценарию:
— войдя в камеру в первый раз, зэк должен изменить состояние лампочки
— войдя в камеру во второй и более раз, зэк должен оставить лампочку, как есть
— каждый зэк, оказавшись в камере в первый раз после дня N должен запомнить состояние лампочки
— каждый зэк, оказавшись в камере во второй раз после дня N должен проверить, поменялось ли состояние лампочки, и если не поменялось — ответить «Да»
— войдя в камеру в первый раз, зэк должен изменить состояние лампочки
— войдя в камеру во второй и более раз, зэк должен оставить лампочку, как есть
— каждый зэк, оказавшись в камере в первый раз после дня N должен запомнить состояние лампочки
— каждый зэк, оказавшись в камере во второй раз после дня N должен проверить, поменялось ли состояние лампочки, и если не поменялось — ответить «Да»
А в это время, главный тюремщик смотрит за тем кто первый выключит лампочку, как только ее выключили, берем следующего случайно, потом повторяем предыдущего (который выключил), не более чем через 200 дней, задаст вопрос на хабре «как убить бессмертных эльфов»
Я бы ответил «мне пофиг» ибо ещё не решил лучше умереть в тайге от голода, или холода, или лучше чтобы просто пристрелели.
В общем, так.
Первый зэк в первый день выключает свет и закручивает лампочку до конца.
Заходит зэк. Если зэк уже тут был, то сразу выходит.
else:
Eсли выключатель в положении «выкл» (как узнать читаем дальше), то крутим по часовой стрелке на «1 час». т.к. часов — 12 (это то, на сколько зэк может на глаз повернуть лампу), а оборотов лампа может сделать, пока не открутится, скажем, 5, то имеем 60 положений лампы.
Если выключатель в положении «вкл», то крутим обратно. Теперь положений получается 120. И никаких проблем :)
Как узнать? Как вошли в комнату, закручиваем лампу, одновременно считая, сколько оборотов сделал. тут же видим, включена лампа или нет. Потом возвращаем лампу в исходную и действуем по алгоритму.
Т.е. как только сотый зэк заходит в комнату, всё становится ясно сразу.
Первый зэк в первый день выключает свет и закручивает лампочку до конца.
Заходит зэк. Если зэк уже тут был, то сразу выходит.
else:
Eсли выключатель в положении «выкл» (как узнать читаем дальше), то крутим по часовой стрелке на «1 час». т.к. часов — 12 (это то, на сколько зэк может на глаз повернуть лампу), а оборотов лампа может сделать, пока не открутится, скажем, 5, то имеем 60 положений лампы.
Если выключатель в положении «вкл», то крутим обратно. Теперь положений получается 120. И никаких проблем :)
Как узнать? Как вошли в комнату, закручиваем лампу, одновременно считая, сколько оборотов сделал. тут же видим, включена лампа или нет. Потом возвращаем лампу в исходную и действуем по алгоритму.
Т.е. как только сотый зэк заходит в комнату, всё становится ясно сразу.
делим время на равные промежутки времени по 100 дней.
каждый заключенный получает свой номер от 1 до 100.
лампа изначально выключена.
если заключенный № N входит в камеру в N-ый день периода, то он включает лампочку.
если любой другой заключенный видит, что лампа включена, то он ее выключает и вносит в свой список вошедших заключенных.
если список заключенного будет заполнен, то он со спокойной совестью может сказать тюремщику «Да».
каждый заключенный получает свой номер от 1 до 100.
лампа изначально выключена.
если заключенный № N входит в камеру в N-ый день периода, то он включает лампочку.
если любой другой заключенный видит, что лампа включена, то он ее выключает и вносит в свой список вошедших заключенных.
если список заключенного будет заполнен, то он со спокойной совестью может сказать тюремщику «Да».
лимитное решение! Отлично, вы второй, кто его нашел!
притом если «любой другой заключенный» заходит в свой N день, он оставляет лампу включённой для ускорения процесса?
Проблема в том, что таким образом будет куча заключённых с разными записями в «списке»
Проблема в том, что таким образом будет куча заключённых с разными записями в «списке»
«Список» не один, а по числу заключенных. Соответственно разных записей не будет — у каждого свой список без коллизий.
Так и я о том. Т.е. нет синхронизации между списками, что затягивает процесс… Продумать бы её =)
На то и лимитное :) В пределе все выйдут со 100% вероятностью.
вот более оптимальный вариант: habrahabr.ru/blogs/zadachki/69642/#comment_1984847
Так как зеки бессмертные, то в первый же день первый же зек говорит «Да» и их всех выпускают не сумев убить. :)
Ну, кроме алгоритмического решения со счётчиком, мне пришло в голову, что 1ого числа они могли друг-друга поубивать так, чтобы их осталось всего 2-е о_О. Кто зашел вторым — говорит, что все прошли… даже лампочку можно не использовать =)
Бит памяти не один.
Нужно ещё ж счётчики хранить.
У них один бит общей shared памяти.
Нужно ещё ж счётчики хранить.
У них один бит общей shared памяти.
Кстати, нашел про лампочку еще задачку :)
Имеется две полностью изолированные друг от друга комнаты. Свет и звук не проходят между ними. В одной комнате висит лампа. Во второй комнате – 5 выключателей. Только один из них включает лампу.
Задача: определить какой выключатель подключен к лампе. Два человека договариваются об алгоритме тестирования. У них есть только одна попытка: они один раз расходятся для проведения опыта по комнатам, затем встречаются и уже точно знают какой выключатель включает лампу. При этом экспериментаторы не пользовались никакими инструментами (сотовый телефон, часы, секундомер и т.п.).
Как им это удалось? Каков был алгоритм проверки выключателей?
Имеется две полностью изолированные друг от друга комнаты. Свет и звук не проходят между ними. В одной комнате висит лампа. Во второй комнате – 5 выключателей. Только один из них включает лампу.
Задача: определить какой выключатель подключен к лампе. Два человека договариваются об алгоритме тестирования. У них есть только одна попытка: они один раз расходятся для проведения опыта по комнатам, затем встречаются и уже точно знают какой выключатель включает лампу. При этом экспериментаторы не пользовались никакими инструментами (сотовый телефон, часы, секундомер и т.п.).
Как им это удалось? Каков был алгоритм проверки выключателей?
N-ый выключатель нужно N раз включить-выключить. Номер работающего выключателя = количеству световых вспышек.
Мне кажется вариантов много, но, например, такой:
1)
Все выключатели выключены
00000
2)
Включается пятый(1-й вариант)
00001
Выключаются все
00000
Делается два моргания лампочкой
11111
00000
11111
00000
3)
Вклчюается четвертый( 2-й вариант)
00010
Выключаются все
00000
Делается два моргания
11111
00000
11111
00000
3)
тоже самое с 00100
…
Имеем — 5 промежутков — два моргания между каждым.
Потом спрашиваем на какой раз было три( если вначале или в конце) или 5( если в середине) морганий подряд.
1)
Все выключатели выключены
00000
2)
Включается пятый(1-й вариант)
00001
Выключаются все
00000
Делается два моргания лампочкой
11111
00000
11111
00000
3)
Вклчюается четвертый( 2-й вариант)
00010
Выключаются все
00000
Делается два моргания
11111
00000
11111
00000
3)
тоже самое с 00100
…
Имеем — 5 промежутков — два моргания между каждым.
Потом спрашиваем на какой раз было три( если вначале или в конце) или 5( если в середине) морганий подряд.
тут все просто: они договариваются о включении выключателей в определенное время и смотрят, когда лампа загорится.
В классике я слышал немного другие условия — 3 переключателя и 1 экспериментатор. Щелк первым на 5 секунд, выключили первый, щелк вторым и заходим — если теплая — значит 1, если горит — 2, если холодная и не горит — 3. Как-то так :)
зэки нумеруются от 1 до 100. дни тоже нумеруются от 1 до 100 и циклически повторяются.
условимся, что если лампочка горит в день номер X равнозначно тому, что все зэки с номерами 1..X уже побывали в камере.
каждый зэк помнит максимальный номер дня, когда он видел лампочку включенной. изначально у всех зеков z(n) = 0
соответственно, если зэк с номером Z попадает в камеру в день D, то алгоритм его действий таков:
если лампочка горит (значит зеки 1..D-1 уже побывали в камере)
{
если z(Z) > D (зек видел лампочку включенной в более поздний день), то оставляет ее гореть
если Z == D (зек попал в камеру в «свой» день), то тоже оставляем лампочку гореть
если z(Z) < D то обновляем свое знание z(Z) = D и выключаем лампочку (зек запоминает, что видел в этот день лампочку включенной)
}
если лампочка не горит, но зек видел ее включенную в этот день (z(Z) > D), то он включает ее
таким образом если вдруг зек 100 в день номер 100 попадет в камеру и застанет лампочку горящей, то можно утверждать что все тут уже побывали
условимся, что если лампочка горит в день номер X равнозначно тому, что все зэки с номерами 1..X уже побывали в камере.
каждый зэк помнит максимальный номер дня, когда он видел лампочку включенной. изначально у всех зеков z(n) = 0
соответственно, если зэк с номером Z попадает в камеру в день D, то алгоритм его действий таков:
если лампочка горит (значит зеки 1..D-1 уже побывали в камере)
{
если z(Z) > D (зек видел лампочку включенной в более поздний день), то оставляет ее гореть
если Z == D (зек попал в камеру в «свой» день), то тоже оставляем лампочку гореть
если z(Z) < D то обновляем свое знание z(Z) = D и выключаем лампочку (зек запоминает, что видел в этот день лампочку включенной)
}
если лампочка не горит, но зек видел ее включенную в этот день (z(Z) > D), то он включает ее
таким образом если вдруг зек 100 в день номер 100 попадет в камеру и застанет лампочку горящей, то можно утверждать что все тут уже побывали
Вообще-то задача даже не подобная, а концептуально идентичная, не интересно.
сначала зэки договариваются кто будет считать количество побывавших в камере с лампочкой.
далее алгоритм такой:
если зэк попал в камеру и лампочка выключена — он ее включает, а если она уже включена ждет следующего раза когда лампочка будет выключена.
зэк может включить лампочку только один раз.
главный зэк-счетовод выключает лампочку если она включена и увеличивает количество побывавших в камере на 1.
далее алгоритм такой:
если зэк попал в камеру и лампочка выключена — он ее включает, а если она уже включена ждет следующего раза когда лампочка будет выключена.
зэк может включить лампочку только один раз.
главный зэк-счетовод выключает лампочку если она включена и увеличивает количество побывавших в камере на 1.
Интерессено, если что такое «Высшая мера наказания»? Если смерть то Зэки бессмертные по условию задачи...:) В таком случае все зэки могут говорить нет, а тот который прйдет через сто дней скажет да, и все живые и здоровые пойдут в лес!:)
Сложно зайти плюсануть, откомментить и не прочесть другие коменты. Большое спасибо за задачку!
Бред какой-то, а я думал вы взрослые и умные люди.
habrahabr.ru/blogs/zadachki/69558/#comment_1981995 под задачей может быть очень взрослая и программерская тема.
Пришёл к такому же мнению. Но есть проблема — по условию не дано начальное состояние лампочки. Если лампочка была изначально включена и в комнату зашёл «пахан», то он решил, что в комнате кто-то уже был и посчитает его, что может оказаться роковой ошибкой.
Бит — но не двоичный. Лампочку можно нагревать и поворачивать на различный угол. ;)
Задача нагло сперта отсюда =)
Ну собственно там и решение есть.
Ну собственно там и решение есть.
мне больше нравится вариант, что она нагло сперта с университета Беркли. www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
А решений есть штук 15
А решений есть штук 15
Задача с Московской математической олимпиады 2003 года:
olympiads.mccme.ru/mmo/2003/resh/9.htm
olympiads.mccme.ru/mmo/2003/resh/9.htm
Ну вот, 3 источника уже нашли =)
Да, кстати, на Эрудиторе прямо говорится, что задача с этой олимпиады
Да, кстати, на Эрудиторе прямо говорится, что задача с этой олимпиады
Ага, и на Хабре, что самое удивительное, она то же уже была habrahabr.ru/blogs/zadachki/11481/
ЗЫ на той олимпиаде я ее решил =)))
ЗЫ на той олимпиаде я ее решил =)))
Совсем нет, по ссылке задача много проще — там заключённым известно, что лампочка изначально выключена. Эта деталь крайне важна. Задача топикстартера же не решается вовсе. Объяснение нерешимости примерно такое — так как начальное состояние неизвестно, то, прочитав состояние лампочки, мы не сможем узнать, была ли передана какая-либо информация через неё или нет. А без передачи информации между узниками задача не решается.
через 10 000 дней можно и так, любому желающему, сказать что все, баста, все уже побывали и с вероятностью в 99% быть освобожденным.
(вероятность того, что каждый конкретный заключенный ни разу за 10 000 дней не побывает в камере = 0,01 процент, суммарно, для 100 заключенных = 1%)
(вероятность того, что каждый конкретный заключенный ни разу за 10 000 дней не побывает в камере = 0,01 процент, суммарно, для 100 заключенных = 1%)
кстати можно чуть-чуть ускорить освобождение по методу «счетчика».
1-й день: Первый зек включает лампочку, если она была выключена.
2: Второй зек, если он не был в первый день, выключает лампочку.
3: Третий зек, если он не был в первый и второй день включает лампочку, а становится «счетчиком» с +2, что потенциально сократит время пребывания в тюрьме на 100 или даже 200 дней.
Если на третий день лампочка включена, или сам «счетчик» был два или три раза, то +2 не получилось, возвращаемся к плану «А» )
1-й день: Первый зек включает лампочку, если она была выключена.
2: Второй зек, если он не был в первый день, выключает лампочку.
3: Третий зек, если он не был в первый и второй день включает лампочку, а становится «счетчиком» с +2, что потенциально сократит время пребывания в тюрьме на 100 или даже 200 дней.
Если на третий день лампочка включена, или сам «счетчик» был два или три раза, то +2 не получилось, возвращаемся к плану «А» )
Еще, на основании этого способа, есть способ специально для людей, которые не живут вечно и понимают, что 30 лет никто из них не переживет:
1: зек_1 включает лампочку
2: зек_2 выключает лампочку, либо, если он был и в первый день, оставляет ее гореть.
далее, если лампочка «сбилась» каждый переключает ее в «неправильное» положение до 100-го дня.
Если на сотый день лампочка будет выключена (в «правильном» положении), значит каждый побывал в камере всего одни раз, и можно выходить на свободу. Если лампочка горит, значит кто-то был, как минимум, дважды. Все обнуляется, и запускаем алгоритм сначала.
Вероятность, к сожалению, просчитать не могу, но определенно какой-то шанс выйти уже на сотый день должен радовать душу заключенных, которые не хотят ждать 30 лет. А по истечении 30-ти летнего срока (10 000 дней) попробовать выйти с 99% вероятностью (см мой пост выше), что тоже неплохо.
1: зек_1 включает лампочку
2: зек_2 выключает лампочку, либо, если он был и в первый день, оставляет ее гореть.
далее, если лампочка «сбилась» каждый переключает ее в «неправильное» положение до 100-го дня.
Если на сотый день лампочка будет выключена (в «правильном» положении), значит каждый побывал в камере всего одни раз, и можно выходить на свободу. Если лампочка горит, значит кто-то был, как минимум, дважды. Все обнуляется, и запускаем алгоритм сначала.
Вероятность, к сожалению, просчитать не могу, но определенно какой-то шанс выйти уже на сотый день должен радовать душу заключенных, которые не хотят ждать 30 лет. А по истечении 30-ти летнего срока (10 000 дней) попробовать выйти с 99% вероятностью (см мой пост выше), что тоже неплохо.
Вероятность при таком подходе в 99 раз ниже, чем в варианте с 30 годами…
да, согласен. Наверное даже не в 99 раз, а гораздо больше. По крайне мере написанный алгоритм довел каунтер дней до 100 миллионов, так и не «выпустив узников».
Единственное, что в моем алгоритме смущает — каунтер не разу не поднялся выше 40-ка, хотя до этого порога доходит очень часто. Может быть это какое-то встроенное ограничение в rand().
может кто-то из программистов подскажет?
Единственное, что в моем алгоритме смущает — каунтер не разу не поднялся выше 40-ка, хотя до этого порога доходит очень часто. Может быть это какое-то встроенное ограничение в rand().
может кто-то из программистов подскажет?
тут всего лишь 2 варианта гарантированого решения:
1. Есть счетчик как в примере по олимпиаде habrahabr.ru/blogs/zadachki/69558/#comment_1983026
2. Каждый раз в 100 дней побывает 1 раз в камере. (Каждый месяц выключать свет. Включать, если второй раз в камеру за 100 дней зашел)
Вероятности не считал.
1. Есть счетчик как в примере по олимпиаде habrahabr.ru/blogs/zadachki/69558/#comment_1983026
2. Каждый раз в 100 дней побывает 1 раз в камере. (Каждый месяц выключать свет. Включать, если второй раз в камеру за 100 дней зашел)
Вероятности не считал.
2. За 100 дней в камере побывает каждый, ровно 1 раз. (Каждый 100-й день тушить лампочку, кто побывает 2й раз за 100 дней — лампочку включает)
не, есть еще одно гарантированное решение. Можно каждые 100 дней включать лампу.
В промежутке же ста дней выключать её, если зэк пошел второй или более раз.
Таким образом ждать момента, когда наступит стодневка, в которую каждый зек побывает в комнате единожды.
не криво объяснил?
В промежутке же ста дней выключать её, если зэк пошел второй или более раз.
Таким образом ждать момента, когда наступит стодневка, в которую каждый зек побывает в комнате единожды.
не криво объяснил?
ой, я ваше же решение и сказал. Пардон. Плюсик вам.
ох уж эти заумные мат. объяснения… «докажем от противного»… по моему проще понять, что каждый вошедший при «свободной» лампочке посылает сигнал счётчику, что он был, его можно засчитывать, а счётчик приняв сигнал опять освобождает лампочку. и так пока каждый не попадёт на «свободную» лампочку и не передаст сигнал.
Как именно вы пошлёте сигнал счётчику? Напомню, что по условию задачи начальное состояние лампочки неизвестно.
До того, как счётчик первый раз зашёл он и не считает.
Заходит первый раз — выключает лампу и начинает считать с единицы (себя).
А остальное много раз описано выше.
Заходит первый раз — выключает лампу и начинает считать с единицы (себя).
А остальное много раз описано выше.
Тогда все зеки, зашедшие перед счетчиком, будут считать себя уже «посчитанными».
они договариваются, что первый зашедший включает лампочку, первый знает, что он первый т.к. зекам дают день на размышление, потом запускают в день по человеку. зажженая лампочка доходит до счётчика, он её выключает и ставит в своём блокноте 1 :) Зек запоминает что он уже включал и больше не включает и так далее…
Начальное состояние не важно: счетчик — зашедший в первый день. Теряем 1 день времени, но избавляемся от неопределенности состояния.
Я буду 99999-ым человеком, который решил задачу ) да еще крайне не оптимально. Зато простота реализации и понимания.
Решение
1 сентября выбирают зека-счетчика (ЗС). Зеки идут в камеры.
Игра начинается.Лампочку никто не трогает, пока не зайдет 3С.
Решение
1 сентября выбирают зека-счетчика (ЗС). Зеки идут в камеры.
Игра начинается.Лампочку никто не трогает, пока не зайдет 3С.
- Заходит ЗС и включает лампочку.
- Все остальные, кто заходит в камеру с лампочкой, ее выключают, только если остальные заходят в первый раз. Включать лампочку остальным нельзя. Остальные говорят всегда начальнику «Нет».
- ЗС включает лампочку, если он была выключена. и ждет пока ее выключат 99 раз. Когда ЗС видит, что 99 раз ее уже выключили, ЗС говорит «Да».
Здесь нет вероятности. Сказать «Да» можно только честно.
Здесь нет счета дней, так как зеки сидят в камерах без окон.
Здесь нет счета дней, так как зеки сидят в камерах без окон.
каждый зек который ещё небыл приходит и накакивает кучу, те кто были терпят до утра, лампочку ни кто не выключает(ибо поскользнуться или вступить можно)
тот кто насчитал 100 куч вывинчивает лампочку и выкидывает, чтоб потом ментам по кизякам нужно было дойти и вкрутить без света.
тот кто насчитал 100 куч вывинчивает лампочку и выкидывает, чтоб потом ментам по кизякам нужно было дойти и вкрутить без света.
Раз зеки бессмертные, то и высшая мера им не страшна. В худшем случае — прострелят голову и отведут назад в камеру. Предлагаю всем говорить да после 10 декабря. Тогда рано или поздно их не расстреляют, а выпустят.
Предлагаю вариацию задачи с более жесткими на мой взгляд рамками (зато эльфов никаких не надо ;) ).
Особенности условия:
Заключенных всего 3.
В спецкамеру помещают на произвольное время (час, день и т.п.).
Попав в камеру можно попросить включить/выключить свет или сообщить, что двое других здесь уже были, причем фразу надо сказать вовремя, т.е. если двое других в камере уже были, а последний, попав в нее, не сказал об этом — амнистия отменяется.
Каков план действий?
Особенности условия:
Заключенных всего 3.
В спецкамеру помещают на произвольное время (час, день и т.п.).
Попав в камеру можно попросить включить/выключить свет или сообщить, что двое других здесь уже были, причем фразу надо сказать вовремя, т.е. если двое других в камере уже были, а последний, попав в нее, не сказал об этом — амнистия отменяется.
Каков план действий?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реши задачку, используя один бит памяти!