Реши задачку, используя один бит памяти!

    image
    Задача, подобная этой на использование совместных ресурсов:
    1-го сентября 100 бессмертных эльфийских воркутинских зэков постоили на торжественную линейку и предложили им ускорить процесс своего освобождения. Итак, в тюрьме есть камера с висящей лампочкой. Лампочку можно включить или выключить. Каждый день, начиная с 1-го сентября тюремщик будет запускать одного заключённого в эту камеру. В этот момент зэк сможет увидеть, горит ли лампочка.
    У каждого заключенного тюремщик будет спрашивать: «А все ли твои товарищи тут были хотя бы раз?» Если зэк отвечает «нет», игра продолжается.
    Если зэк отвечает «да» и это правда — всех выпускают на волю в тундру. Если же это неправда — высшая мера наказания для всех.
    Тюремщики могут выбирать заключенных вразброс и с повторениями. Заключенные сидят в одиночных камерах и могут договориться только один раз — 1-го сентября на обеде после торжественной линейки. После этого они сидят в «одиночках» без окон, совсем не видят друг друга и лампочки.
    Найти оптимальную стратегию поведения каждого заключенного с тем, чтобы их выпустили пораньше.

    WARNING В коментах появилось два алгоритмических решения, одно вероятностное и одно лимитное. Плюс два-три читерских Есть еще несколько возможных ответах, основанных на довольно сложно поведении зэков. Также всем предлагаю формально оценить время выхода.
    Спасибо xmolex за указание возможного первоисточника! По ссылке — фундаментальный pdf-файлик с 10 решениями и математической оценкой каждого из них!
    UPD вопли «боян» набирают мощь, и не зря — вот та же задача на Эрудиторе, на Московской олимпиаде и (о боже, позор моим поисковым скилам) на Хабре от юзера ttim
    UPD2: для тех кому эта задача и все её решения кажутся легкими, опубликовано продолжение с учетом помех.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 252

      –10
      Начальники развлекаются, придумали себе забаву…
        +2
        Не, это не начальнии, а чуваки из гуглояндексов всяких. Как у вас с решением? Вариантов стратегий много…
          0
          Да чего там думать-то, каждый кто там был на стене ставит метку )))
            +12
            отставить клянчить дополнительные биты!
        –20
        элементарно, каждый из заключённых отмечает каждый прожитый день. кто пойдёт на 100 день в ту камеру, говорит «да» и все радуются и смеются при этом убегая в тундру =)

        P.S. и не говорите мне что это не по заданию, там нет никаких ограничений на такие действия. никто же не сказал, что обязательно использовать эту лампочку — обычно в логических задачах некоторые элементы условия призваны просто запутать решающего.
          +2
          ой-ой-ой с колбасой! «вразброс и с повторениями». Я как тюремщик могу вызывать первые 50 дней первого зека, а вторые 50 дне — второго.
            +18
            вот, блин, опозорился из-за невнимательности. извиняюсь.
              +10
              Зеки договариваются между собой, что оставляют лампочку зажженной только если он здесь был первый раз. Следующий зек, который видит, что лампочка зажжена, гасит ее и считает сколько раз он ее погасил. Если зек пришел, а лампочка не горит и он тут уже был и у него есть счетчик погашенных лампочек (лампочек, которые он погасил), он зажигает лампочку и уменьшает свой счетчик. Тот кто первый наберет 100 на своем счетчике тот и скажет, что все ок.
                +2
                можно немного улучшить алгоритм, если добавить условие:

                если зек тут уже был, но вчера тут не был и позавчера тут не был и лампочка горит, то лампочку он считает, но не выключает (передавая счетчик следующему зеку, который руководствуется тем же правилом.
                  0
                  отлично, это второе алгоритмическое решение! Премия и почести!
                    +1
                    сейчас написал программу и понял что это слишком долго, мое решение ниже лучше.
                      +4
                      полное решение задачи на PHP s-c.me/Mi (где-то через 60000 дней они выйдут)
                        0
                        Хммм… 164 года… интересно это учитано в задаче?
                          0
                          еще как! Бессмертность и эльфичность зэков позволяет им быть неторопливыми
                            0
                            немного подумав, уменьшил среднее время в заключении в два раза, добавив такое условие:

                            Если один зек уже знает, что другой зек тут был, но лампочка в период этого зека не горит, то этот зек сам включает лампочку, чтобы сказать об этом тем, кто этого еще не знает. обновленный исходник: s-c.me/Ml теперь некоторые зеки выйдут даже если они будут не бессмертны!
                            0
                            Вот это habrahabr.ru/blogs/zadachki/69558/#comment_1983053 решение с периодом 100 дней сокращает время заключение до «приемлимых» 80 лет.
                              +2
                              Многовато будет. Бессмертные эльфы помрут со скуки… :)
                      +1
                      решил всетаки запрограммировать, то что я тут написал, и понял что слишком долго зеки будут выходить. Думаю стоит распространить информацию между как можно большим количеством зеков, т.е. договорится что есть так называемый период распостранения информации. т.е. каждый зек, может разговаривать только в свой отрезок, скажем 100 дней, остальные в этот отрезок не должны ничего делать, а просто смотреть на лампочку, зная что если в этом отрезке она горит, то это зек номер N ее включил, так как там был итого нужно около 100*Period дней чтобы хотябы один зек увидел все лампочки от всех зеков.
                        +1
                        да, забыл сказать каждый 100й день есть день так называемого сброса информации, зек который приходит в этот день выключает лампочку полюбому. Если 100*Period дней не хватит, то все повторяется.
                          +1
                          Это было лимитное решение!!! В пределе получается, что они выйдут. Поздравляю. Остались только очень злокозненные варианты.
                          Кстати, когда я додумался до этого решения, я не смог оптимизировать период. Есть идеи?
                            +1
                            Думаю 100*2 оптимально для rand функции. Дает возможность каждому зеку увидеть лампочку. Для 200 получается 60 тысяч дней для 100 получается 100 тысяч дней
                          0
                          Допустим, мы водим двух зеков.
                          1. Зек №1 — вкл
                          2. Зек №2 — вкл
                          3. Зек №1 — выкл
                          4. Зек №2 — вкл
                          5. Зек №1 — выкл

                          20х (лень считать). Зек №1/2 — расстрел.
                            +1
                            Согласен, тут оптимизация не прокатит, пока писал программу, тоже это увидел. Решение с лимитами по-моему оптимально.
                            +1
                            или я чего-то не понимаю, или тут используется сильно больше одного бита памяти :)
                        • UFO just landed and posted this here
                            +1
                            а кого-то могут вообще не выбрать никогда…
                              +1
                              Нет. Вероятность 1/100, а не 0. Это важно.
                                +3
                                в условиях ничего про вероятность нет. только произвол тюремщиков…
                                  +1
                                  В таком случае задача теряет смысл. Получается вариант троллинга с заранее некорректным условием задачи. Но данное условие (равновероятности) учитывается и приносит плоды в виде интересных решений.
                          +1
                          Если считать, что лампочка видна остальным заключенным, решение такое: все, кто был в камере первый раз включают лампочку, если того же заключенного ведут во второй раз — выключают. Соотв-но, если в общей сложности лампочка будет гореть 100 дней, все заключенные побывали в камере, можно говорить «да» :)
                            0
                            лампочка видна только приходящему в комнату зеку в момент его прихода в комнату.
                              +1
                              Жаль… Тогда счетчик, как предложили ниже :)
                            +1
                            Лампочка тут видимо не спроста =)
                              +1
                              это ваш бит памяти!
                              +1
                              Да было это уже на хабре. trueClearThinker написал правильно. Единственное, что он не упомянул — назначить одного человека «счётчиком» горящих лампочек, которые после 99 раз говорит «да».
                                +2
                                Есть решение со счетчиком, но это не решение trueClearThinker. Вот глядите:
                                Пусть счетчик — зэк номер 0100.
                                Изначально лампа выкл.
                                1-й день — заходит зэк 0001. Лампа вкл
                                2-й день — заходит зэк 0001. Лампа выкл
                                3-й день — заходит зэк 0002. Лампа вкл
                                4-й день заходит зэк 0100. Видит включенную лампу. Что он посчитает, увидев вкл. лампу? Что один чувак был тут впервые. И все.
                                  0
                                  А точнее мы имхо определить не сможем, в любом случае многим придется ходить по много раз, пока счетчик все не посчитает правильно. Но это лучше чем расстрел :)
                                    +1
                                    но глядите — информация о том, что зэк 0001 был в камере теряется.
                                      0
                                      Да, и теоретически может быть ситуация когда все побывают, но об этом так и не узнают. Так что все в итоге сведется к подбрасыванию монетки. Надо похоже думать что то еще.
                                        0
                                        не подглядывайте только в коменты снизу. Хочется новых решений!
                                    +3
                                    2 день — неверно.
                                    Зэк включает лампу только если она выключена и только если он тут первый раз.
                                    Выключать лампу может только счётчик.
                                      0
                                      вот теперь правильно!
                                        +3
                                        Извините, но вы используете не 1 бит памяти. Зек считает сколько раз он выключал, это дополнительная память.
                                          +1
                                          Для обмена информации используется один бит. Промывание мозгов никто зекам не делает.
                                            +1
                                            хорошо, один бит shared памяти
                                          0
                                          > Зэк включает лампу только если она выключена и только если он тут первый раз.
                                          То есть «и только если он её не включал»
                                      +2
                                      Это из «Архипелага ГУЛАГа» в редакции для изучения в классах с лженаукой кибернетикой?
                                        +21
                                        допустим лампочка была включена:

                                        одного зека назначают главным. он только включает лампочку и считает сколько раз он ее включил.
                                        остальные зеки если приходят в первый раз — выключают лампочку. если втрой и более — ничего не трогают.
                                        как только главный зек насчитает 100 — он и скажет что все побывали в этой комнате.
                                          0
                                          да, отличное решение! Сможете оценить вероятность выхода?
                                          Есть еще парочка решений. Одно основано на разбиении вечности на промежутки, найдете?
                                            +1
                                            вероятность 0,01-что выберут конкретного из кучи
                                            вероятность выхода 0,0001 получается.

                                            но тут еще вероятность должна зависеть от того, что главного зека выберут. и он сможет увидеть состояние лампочки. но я не знаю как… не могу вспомнить теорию вероятности.
                                            но вероятность выхода будет намного меньше чем 0,0001, скажем 0,0001/100=0,000001 или вроде того.
                                              +5
                                              Главным будет тот, кого первым введут.
                                                +3
                                                т.е. все остальные зеки если не пошли в первый день — значит они считают себя не главными. хм… верно.
                                                  +1
                                                  Если назначить второго, то будет на один день быстрее.
                                                    +2
                                                    Не второго, а того, кого на второй день поведут.
                                                  +5
                                                  вероятность выхода 1 т.к. время не ограничено.
                                                    +1
                                                    я имел в виду вероятность выхода по прошествии 100 дней.
                                                      –1
                                                      Если использовать подход с включением лампочек при первом заходе, а выключением только счетчиком, то в идеальном случае потребуется по крайней мере 199 дней. Иначе никак. Это в случае, когда заходы новых зеков и счетчика чередуются.
                                                        0
                                                        интересно за что минут. кому-то не нравится вариант со 199 днями? для решения разбиение на интервалы — 101 день нужно (если охранники вызовут всех заключенных по одному разу в первый же интервал). для решения с выключением лампочек счетчиком нужно 199 дней (когда идет чередование зеков и счетчика).
                                                      0
                                                      а я имел ввиду, разумеется, оценку времени выхода, а не вероятность
                                                        +1
                                                        У меня оценка почти в 30 лет получилась: пост
                                                    +1
                                                    Пожалуй присоединюсь к рассуждениям, первое что пришло в голову) В предложенном решении после считывания информации счётчик может либо увеличиться на единицу, либо остаться без изменений.
                                                    Если предположить, что поначалу чаще будут заходить зеки, которые ещё не были в комнате, то можно немного оптимизировать процесс. Например, разобьём дни на группы по четыре, пусть это будут старшие биты послания зеку-счётчику — 00, 01, 10, 11. Младший бит — состояние лампочки (вкл / выкл). Соответственно, когда младший бит == 0, счётчик не меняется, иначе счётчик += 1, за исключением случая когда послание == 111, тогда счётчик += 2. Правда в таком случае если послание == 110, может потеряться информация, но в нашем предположении этот случай менее вероятен, чем 111. По-моему это должно немного ускорить процесс освобождения, насколько конкретно — надо считать. Ну и ещё нужно оценить границы применимости этого предположения, то есть через сколько дней переходить на обычную систему подсчёта. Надеюсь, доступно изложил)
                                                    +1
                                                    забыл добавить, что включать лампочку может тока главный зек. другие если лампочка выключена ее не трогают.
                                                      +1
                                                      Очень не эффективный метод получается. Если считать что всех зеков заводят по порядку или в случайном порядке, счетчик будет попадать в комнату 100 раз. Это 10 000 дней, т.е. 30 лет, у многих срок и так кончиться, другие умрут.
                                                        0
                                                        откровенно говоря, это самый быстрый вариант, который я лично смог найти.
                                                          +1
                                                          > у многих срок и так кончиться, другие умрут.
                                                          а это уже совсем другая история ©
                                                            +1
                                                            поправил условие — даровал зэкам бесконечную жизнь. Или может сделать их эльфами?
                                                              +4
                                                              Можно добавить что бесмертным вокрутинским эльфийским зэкам дали еще и по пожизненному. А то куда им с бессмертием торопится )
                                                                +4
                                                                если они бессмертные — то их казнить не могут. )
                                                                  +4
                                                                  В таком случае поправьте ещё условие «Лампочку можно включить или выключить», добавив «или оставить как есть».
                                                                +1
                                                                а ещё этот способ ломается если посреди эксперимента кто-нибудь умирает — если умрёт человек, ни разу не побывавший в комнате, то все так и будут сидеть ждать.
                                                                  +1
                                                                  1-го сентября 100 бессмертных эльфийских воркутинских зэков постоили на торжественную линейку
                                                                +1
                                                                Но в этом решении ответственный «пахан» должен заходить строго за зеком! за одним зеком! а если между приходами пахана прошли 5 зеков? только первый сделает явное действие, и никто из последующих не включит и не выключит лампочку (как они выключат ее, если она уже выключена?), а они-то ведь уже побывали в камере… четверо значит останутся неучтенными?
                                                                  +1
                                                                  тогда зек думает про себя «что он здесь был» только когда выключил лампочку. для достоверности так сказать.
                                                                  в этом случае главный зек безошибочно посчитает их.
                                                                  +1
                                                                  А если «главного» запустят в камеру всего один раз?
                                                                    +1
                                                                    По условию выбор охранников равновероятен. В случае предвзятого отношения (которое нам не известно) теряется всякий смысл в решении.
                                                                    +1
                                                                    А если главный зэк всего один раз побывает в камере? Как он сможет посчитать?
                                                                      +1
                                                                      Не заметил, что такой вопрос уже задали))
                                                                    +4
                                                                    В блоге «занимательные задачки» была похожая задача. И, да, очень символична аналогия: зеки, 1 сентября, торжественная линейка… автор в школьные годы чувствовал себя как в тюрьме?
                                                                      +1
                                                                      и не один только автор…
                                                                      +1
                                                                      Как-бы боян, ну и Devgru, упомянув про счетчика, фактически открыл всю соль задачи :)
                                                                        +5
                                                                        Можно и заминусовать тот комментарий и соль будет прикрыта :)
                                                                      • UFO just landed and posted this here
                                                                          +1
                                                                          мощно и очень ответственно! Но надо бы стопроцентную гарантию…
                                                                          +1
                                                                          единственный минус такого решения… этот один зек может умереть раньше чем в 100 раз увидит горящую лампочку…
                                                                            +1
                                                                            По условиям задачи — зеки бессмертны.
                                                                              +2
                                                                              бессмертие зэкам было даровано после добавления комментария комментария. (Прям как в рассказе кое что задаром)
                                                                          • UFO just landed and posted this here
                                                                              +13
                                                                              Нет, тот поедет в Воркуту :)
                                                                                +9
                                                                                Гуглаг :)
                                                                                  +1
                                                                                  Я там до 6 лет жил, по 9 месяцев в год. Поверьте, ничего ужасного там нет. :)
                                                                                    0
                                                                                    земляк! А я до 16-ти!
                                                                                      +1
                                                                                      Да я не спорю. У меня оттуда знакомы были — отличные ребята. Тем более, там уголь, на моей родине — уголь, темы знакомые есть :)
                                                                                  +9
                                                                                  Каждый зек при первом попадании в камеру включает лампочку, если та была выключена (кстати, в задаче не сказано, что включать/выключать могут только зеки) :), затем надкусывает палец или губу и оставляет на стене пятно крови. Если видит рядом еще 99 пятен — зовет начальника и на свободу с чистой совестью :)
                                                                                    +4
                                                                                    каждый зек попадая первый раз в комнату ставит себе на лбу ожог лампочкой. После 1-го сентября после и после проверки что у всех есть ожог, первый заходящий зек говорит да.
                                                                                      +2
                                                                                      Хм… Обычный двоичный семафор. К чему зэки и всякие воркутинские обвязки? Один процесс считает сигнальные события, другие ему сигналят однократно. И всё.
                                                                                        +1
                                                                                        Вот поэтому-то так и отбирают хороших программистов! Чтобы за воркутинской пеленой предметной области увидеть привычные семафоры
                                                                                          +3
                                                                                          Нуу… Чё-то не считаю я себя хорошим программистом. Шаблоны проектирования не использую, C++ не люблю, ООП считаю происками империализма, тормозящего научно-технический прогресс, и так далее :) Скорее уж так отбирать надо программистов, которые читают книжки по параллельном программированию :)
                                                                                      • UFO just landed and posted this here
                                                                                          0
                                                                                          Самое простое решение на день № 100^100-1 включить лампу, а на следующий сказать Да и все =) Или просто в последний день сказать Да.
                                                                                            0
                                                                                            последнего дня нет!
                                                                                            Тюремщик может вызывать все 100^100-1 одного и того же зека
                                                                                              +1
                                                                                              Тогда смысл задачи теряется, если он так будет делать.
                                                                                                +1
                                                                                                Но у тюремщика есть функция Random(); поэтому он будет выбирать псевдослучайно.
                                                                                                  0
                                                                                                  но уже есть устойчивые к этому решения!
                                                                                                  +1
                                                                                                  Ой точно, бедный зек в таком случае (
                                                                                                    +1
                                                                                                    особенно, если он будет применять стратегию с ожогами или каплями крови.
                                                                                                      +1
                                                                                                      нормальный такой суровый воркутинский эльфийский бессмертный зек =)
                                                                                                +10
                                                                                                1) когда зек заходит впервые и лампочка Не горит — он её включает, если горит, то зек считает что он и не заходил и ждёт положения когда он войдет при выключенной лампочке.
                                                                                                2) подсчет включенных лапочек и их выключение производится счетчиком. он должен 99 раз выключить лампочку. и он же говорит «да», когда попадет к лампочке вновь.
                                                                                                  +1
                                                                                                  Да, вы нашли аглоритмическое решение задачи и будет премированы! Теперь оценка времени.
                                                                                                  И найдите же кто-нибудь другие решения!!!
                                                                                                    +3
                                                                                                    Пусть 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 лет
                                                                                                  +1
                                                                                                  я думаю, что выпуск в тундру «на свободу» для зэков равносилен высшей мере… попробуй в робе протопай 100-200 км до ближайшего жилья…
                                                                                                  • UFO just landed and posted this here
                                                                                                      0
                                                                                                      тогда их не должна волновать «высшая мера» которой им грозят охранники — всем говорить «ДА»
                                                                                                    +18
                                                                                                    Представляете, и тут, в самый ответственный момент, лампочка перегорает!
                                                                                                      +1
                                                                                                      лампочке тоже бессмертие подарить
                                                                                                      +2
                                                                                                      Насколько я понимаю, формально можно вычислить искомое время лишь с определенной достоверностью, скажем 99%. Ибо даже рандомный охранник может выбрать одного и того же зека 100 раз подряд с вероятностью 0,5^100 (7,8х10-31).
                                                                                                      (Вспомнилась цитата с баша про то, как препод по терверу 5 раз бросил монетку орлом).
                                                                                                        +5
                                                                                                        Так как заключенные могут договориться только 1 сентября после торжественной линейки, они просто дожидаются, как пройдет год и на торжественном обеде спрашивают друг друга кто видел лампочку, а кто нет. Если нет, то ждут следующий год.
                                                                                                          +2
                                                                                                          Правильно. Это будет быстрее чем 30 лет зеков по камерам гонять.
                                                                                                            +2
                                                                                                            вот чёрт! Вы нашли лазейку в моём речевом витийстве!
                                                                                                            +3
                                                                                                            >Есть еще предельное (lim'итное) и социальное

                                                                                                            Первый вошедший в камеру зек должен сказать «Да». Это будет самое быстрое социальное решение.
                                                                                                            • UFO just landed and posted this here
                                                                                                                +1
                                                                                                                Ну почему же, еще как катит, во первых в этом случае зэки сами выбирают смерть чтобы не мучаться иллюзией надежды. Да и охраникам проще их убить. И для общества хорошо, зэков содержать не нужно.
                                                                                                                  +1
                                                                                                                  И их всех казнят. Задача решена в кратчайшие сроки. Все условия выполнены. Ведь они покинут тюрьму. Где мой приз — поездка в Воркуту :)

                                                                                                                  Ну а если серьезно, может например зек который зашел в камеру первый раз должен снять с себя правый носок. Потом просто надо посчитать сколько носков уже лежит в камере и сделать вывод. А если ответ должен быть дан до того как он посчитает носки, то можно например первого сентября посчитать по ногам, сколько зеков без носок. и если уже все, то ответить «да».
                                                                                                                +1
                                                                                                                ну так как зеки у нас «бессмертные эльфийские воркутинские» то можно так:
                                                                                                                первый день первый зек включает лампочку
                                                                                                                каждый, кто заходит первый раз лампочку не трогает
                                                                                                                кто заходит второй раз выключает лампочку
                                                                                                                каждый зек считает до 100
                                                                                                                на 100й день если лампочка горит, то это означает, что все были по одному разу говорит «ДА»
                                                                                                                если на 100ое посещение лампочка не горит, то включает и говорит «НЕТ»
                                                                                                                все поняв, что он сказал «НЕТ» на 100 день делают вывод, что кто-то побывал в эти 100 дней там не один раз… начинаем все заново

                                                                                                                очень неоптимально, но когда-то должно случиться, что за 100 дней каждого сводят туда по одному разу!
                                                                                                                  0
                                                                                                                  да, это ацки математичное решение. Вы его нашли, ура!
                                                                                                                    0
                                                                                                                    А разве зеки знают про количество прошедших дней? В условии же — одиночки «без окон»…
                                                                                                                      0
                                                                                                                      блин! Опять прогадал, добавив условия. Без окон — чтобы не видели через них лампочку. А дни определять можно по завтраку.
                                                                                                                  0
                                                                                                                  Один из преступников только выключает свет, а остальные только включают его. Преступник-выключатель подсчитывает выключения и на основании их количества делает вывод о числе «нормальных преступников» отбывших наказание.
                                                                                                                    +7
                                                                                                                    Первого сентября на линейке зэки договариваются о том, кто из них будет главным. Потом все они (кроме главного) дружно разбивают себе головы об угол тюремной камеры.

                                                                                                                    Единственный выживший зэк может спокойно идти в комнату с лампой и сказать, что мол, да, теперь все в комнате с лампочкой побывали.
                                                                                                                      0
                                                                                                                      Бессмертные же зэки то )
                                                                                                                        0
                                                                                                                        Там было бессмертные приментительно к продолжительности жизни. И потом, если они бессмертны, то «смертная казнь» в условии для них не имеет смысла )
                                                                                                                      • UFO just landed and posted this here
                                                                                                                          +2
                                                                                                                          Вы видимо нашли то самое «социальное решение», про которое писал автор :))
                                                                                                                        0
                                                                                                                        На вопрос «А все ли твои товарищи тут были хотя бы раз?» можно ответить «Да, все, потому что у меня нет товарищей»
                                                                                                                          0
                                                                                                                          Блин, опоздал на три минуты :(
                                                                                                                          0
                                                                                                                          Написал на php решение чтобы точно подсчитать количество дней.
                                                                                                                          Всегда выходит между 8000 — 12000 дней.
                                                                                                                          Долго однако =). Может сделать вариант с двумя лампочками?
                                                                                                                          • UFO just landed and posted this here
                                                                                                                            • UFO just landed and posted this here
                                                                                                                              0
                                                                                                                              Ты забыл что можно каждые 365 дней актуализировать значение $switches (людей которые были в комнате и которых посчитал главный), увеличивая его на то число, которое главный посчитает 1ого сентября на общей линейке. Я думаю, что число упадет до 1,5-2 т. дней…
                                                                                                                                0
                                                                                                                                По поводу 365 дней… А разве тогда вобще есть смысл в подсчете если через 365 дней можно спросить у каждого был ли он там?
                                                                                                                                • UFO just landed and posted this here
                                                                                                                                    0
                                                                                                                                    Мне почему то кажется что это не сойдется с задачей :(
                                                                                                                                    • UFO just landed and posted this here
                                                                                                                                0
                                                                                                                                тогда это будет задачка про маркса (ссылка в начале)
                                                                                                                                +1
                                                                                                                                Надо в эту тюрьму Майкла Скофилда посадить. Через неделю будет массовый prison break :)
                                                                                                                                  0
                                                                                                                                  боюсь на 100 зэков никаких сцилл не наберёшь
                                                                                                                                  +9
                                                                                                                                  2 февраля 1999 года Конституционный суд России вынес Постановление № 3-П, в котором признал неконституционным возможность вынесения смертных приговоров в отсутствие судов присяжных во всех регионах страны.
                                                                                                                                  Согласно УК РФ смертная казнь в порядке помилования может быть заменена пожизненным заключением или сроком лишения свободы на 25 лет. Для отбывающих пожизненное заключение в России действует всего три специальные колонии: на острове Огненном Вологодской области, близ поселка Лозьва в Свердловской области и в Мордовии.
                                                                                                                                  Мы же имеем дело с воркутинскими заключенными — значит их высшая мера — 25 лет. При алгоритмическом варианте решения этой задачи пришлось бы ждать около 30 лет. Так что сказать в первый же день нет и подождать всего:) 25 лет — гораздо более эффективный выход из данной ситуации.
                                                                                                                                  • UFO just landed and posted this here
                                                                                                                                      +3
                                                                                                                                      Это лучший ответ из всех прозвучавших!
                                                                                                                                      +1
                                                                                                                                      Бессмертным зэкам 7 лет расстрела с конфискацией :)

                                                                                                                                      Есть мысля навеяная Slotted Aloha.
                                                                                                                                      Считаем выключенную лампочку collision'ом.
                                                                                                                                      Slot — среднестатистический промежуток времени за который все должны побывать внутри.
                                                                                                                                      Начальный статус лампочки — вкл.

                                                                                                                                      После первого слота если зашедший зэк в комнате впервой он выключает лампочку, до следующего слота лампочку никто не трогает. Первый кто заходит в начале следующего слота включает её. Собственно можно говорить стражнику «Да» если лампочка остаёться включенной до конца слота. Сумбурно, но думаю мысль сумел передать.
                                                                                                                                        +2
                                                                                                                                        www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
                                                                                                                                        • UFO just landed and posted this here
                                                                                                                                            0
                                                                                                                                            Инженеру необязательно изобретать велосипеды. Есть задача. Инженер должен сопоставить затраты на выполнение задачи. Если эту работу проделал уже кто-либо другой и меня устраивает результат, то зачем мне тратить n-ное количество времени на то, что можно решить быстрее, воспользовавшись чьим-то трудом?
                                                                                                                                            Человек задал существующую (уже известную в мире) задачу, придуманную не им. Почему я не могу воспользоваться решениями, просчитанными не мной?
                                                                                                                                            • UFO just landed and posted this here
                                                                                                                                                0
                                                                                                                                                Заметьте, что я не стал присваивать решение себе.
                                                                                                                                                Вспомните загадку «Зимой и летом одним цветом». Думаю, что вы не сами догадались, что это ель, а вам кто-то когда-то сказал. Если бы я задал такую задачку на хабре, глупо полагать, что вы бы сами думали. Вы бы ответели ответом, который вы когда-то узнали. Я поступил также. Повторюсь, что задаче в обед сто лет.
                                                                                                                                                  0
                                                                                                                                                  ничего страшного! Вы получили удовольствие, решая её? Тогда моя миссия выполнена!
                                                                                                                                            0
                                                                                                                                            большое спасибо за ссылку! Честно говоря, мне задачку одна девушка на работе задала. Кину ссылку на первоисточник!
                                                                                                                                            Но цель-то была заставить всех поломать мозги, а не погуглить.
                                                                                                                                              0
                                                                                                                                              Думаю, автор очень много времени убил на эту работу, так что разобратся в ней это тоже мозги напрячь надо. Тем более там ещё куча открытых вопросов, ну и для хорошести надо доказать, что алгоритм явлетяся самым оптимальным.
                                                                                                                                              0
                                                                                                                                              Фундаментальный труд!
                                                                                                                                              0
                                                                                                                                              Предположим, что охранники непредвзятые и преставляют собой «классический» псевдослучайный алгоритм.
                                                                                                                                              Тогда можем решить задачу эмпирическим путем — программно 100000 раз просимулировав псевдослучайный выбор в массиве из 100 элементов, и для верности взяв максимальное значение.

                                                                                                                                              получась маленькая программка (на ruby), которая за 5 минут посчитала 100тыс итераций, и выдала максимальное значение = 1795 дней.

                                                                                                                                              Если зэки очень хотят остаться живыми — то они могут это число и увеличить раз эдак в 100. Всё равно же бессмертные :)

                                                                                                                                              этот алгоритм зэки могут выбрать если:
                                                                                                                                              а) они не дружные зэки, и так и не смогли договориться кто из них главный :)
                                                                                                                                              б) в какой-то момент лампочка перегорела, и, в условиях кризиса, финансирование не позволяет поставить новую :))
                                                                                                                                              в) их всех устраивает <0.[..]1% вероятноcть погибнуть
                                                                                                                                              • UFO just landed and posted this here
                                                                                                                                                0
                                                                                                                                                первый зек — включает лампочку
                                                                                                                                                каждый последующий зек при заходе в камеру:
                                                                                                                                                1) если он там уже был — «переключает», тоесть зажигает горящую или тушит горящую
                                                                                                                                                2) если не был — свет не трогает
                                                                                                                                                при этом каждый зек считает дни с 1 сентября и при входе анализирует
                                                                                                                                                сколько «уникальных посещений» было в камере.
                                                                                                                                                дальше пока не знаю…
                                                                                                                                                • UFO just landed and posted this here
                                                                                                                                                    0
                                                                                                                                                    была какая-то логическая задачка, тоже с комнатой и лампочками и там
                                                                                                                                                    можно было понять что с ламочкой было — потрогав ее — если горела до этого — значит теплая, может это тоже тут как-то подойдет)))
                                                                                                                                                      0
                                                                                                                                                      идея неплохая, но за сутки остынет.
                                                                                                                                                      Я вот еще думал, как-то применить четность дня… Но почитал ответ, который по ссылке выше…
                                                                                                                                                        0
                                                                                                                                                        Полагаю, что за день остынет.
                                                                                                                                                    0
                                                                                                                                                    Если вероятность появления зэка в камере в любой день 1/100, то задачу можно решить так: вычислить мат. ожидание события «все зэки побывали в комнате с лампочкой» (это будет некое числи N, сейчас уже не помню, как его считать, но думаю, что-то около 1000). Зэки должны считать дни своего заключения. После наступления дня N зэки должны действовать по следующему сценарию:

                                                                                                                                                    — войдя в камеру в первый раз, зэк должен изменить состояние лампочки
                                                                                                                                                    — войдя в камеру во второй и более раз, зэк должен оставить лампочку, как есть
                                                                                                                                                    — каждый зэк, оказавшись в камере в первый раз после дня N должен запомнить состояние лампочки
                                                                                                                                                    — каждый зэк, оказавшись в камере во второй раз после дня N должен проверить, поменялось ли состояние лампочки, и если не поменялось — ответить «Да»
                                                                                                                                                      0
                                                                                                                                                      А в это время, главный тюремщик смотрит за тем кто первый выключит лампочку, как только ее выключили, берем следующего случайно, потом повторяем предыдущего (который выключил), не более чем через 200 дней, задаст вопрос на хабре «как убить бессмертных эльфов»
                                                                                                                                                        –1
                                                                                                                                                        Я бы ответил «мне пофиг» ибо ещё не решил лучше умереть в тайге от голода, или холода, или лучше чтобы просто пристрелели.
                                                                                                                                                          –3
                                                                                                                                                          В общем, так.
                                                                                                                                                          Первый зэк в первый день выключает свет и закручивает лампочку до конца.
                                                                                                                                                          Заходит зэк. Если зэк уже тут был, то сразу выходит.

                                                                                                                                                          else:

                                                                                                                                                          Eсли выключатель в положении «выкл» (как узнать читаем дальше), то крутим по часовой стрелке на «1 час». т.к. часов — 12 (это то, на сколько зэк может на глаз повернуть лампу), а оборотов лампа может сделать, пока не открутится, скажем, 5, то имеем 60 положений лампы.

                                                                                                                                                          Если выключатель в положении «вкл», то крутим обратно. Теперь положений получается 120. И никаких проблем :)

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

                                                                                                                                                          Т.е. как только сотый зэк заходит в комнату, всё становится ясно сразу.
                                                                                                                                                            +1
                                                                                                                                                            Так можно просто свое имя кровью на стене писать. Ну или номер порядковый. Это читерский метод)
                                                                                                                                                              +1
                                                                                                                                                              это вы воспользовались лишними shared-битами
                                                                                                                                                              +2
                                                                                                                                                              делим время на равные промежутки времени по 100 дней.
                                                                                                                                                              каждый заключенный получает свой номер от 1 до 100.
                                                                                                                                                              лампа изначально выключена.
                                                                                                                                                              если заключенный № N входит в камеру в N-ый день периода, то он включает лампочку.
                                                                                                                                                              если любой другой заключенный видит, что лампа включена, то он ее выключает и вносит в свой список вошедших заключенных.
                                                                                                                                                              если список заключенного будет заполнен, то он со спокойной совестью может сказать тюремщику «Да».
                                                                                                                                                                0
                                                                                                                                                                лимитное решение! Отлично, вы второй, кто его нашел!
                                                                                                                                                                  0
                                                                                                                                                                  притом если «любой другой заключенный» заходит в свой N день, он оставляет лампу включённой для ускорения процесса?
                                                                                                                                                                  Проблема в том, что таким образом будет куча заключённых с разными записями в «списке»
                                                                                                                                                                    0
                                                                                                                                                                    «Список» не один, а по числу заключенных. Соответственно разных записей не будет — у каждого свой список без коллизий.
                                                                                                                                                                      0
                                                                                                                                                                      Так и я о том. Т.е. нет синхронизации между списками, что затягивает процесс… Продумать бы её =)
                                                                                                                                                                +2
                                                                                                                                                                Так как зеки бессмертные, то в первый же день первый же зек говорит «Да» и их всех выпускают не сумев убить. :)
                                                                                                                                                                  0
                                                                                                                                                                  Ну, кроме алгоритмического решения со счётчиком, мне пришло в голову, что 1ого числа они могли друг-друга поубивать так, чтобы их осталось всего 2-е о_О. Кто зашел вторым — говорит, что все прошли… даже лампочку можно не использовать =)
                                                                                                                                                                  • UFO just landed and posted this here
                                                                                                                                                                    0
                                                                                                                                                                    Бит памяти не один.
                                                                                                                                                                    Нужно ещё ж счётчики хранить.
                                                                                                                                                                    У них один бит общей shared памяти.
                                                                                                                                                                      +1
                                                                                                                                                                      Кстати, нашел про лампочку еще задачку :)

                                                                                                                                                                      Имеется две полностью изолированные друг от друга комнаты. Свет и звук не проходят между ними. В одной комнате висит лампа. Во второй комнате – 5 выключателей. Только один из них включает лампу.

                                                                                                                                                                      Задача: определить какой выключатель подключен к лампе. Два человека договариваются об алгоритме тестирования. У них есть только одна попытка: они один раз расходятся для проведения опыта по комнатам, затем встречаются и уже точно знают какой выключатель включает лампу. При этом экспериментаторы не пользовались никакими инструментами (сотовый телефон, часы, секундомер и т.п.).

                                                                                                                                                                      Как им это удалось? Каков был алгоритм проверки выключателей?
                                                                                                                                                                        0
                                                                                                                                                                        N-ый выключатель нужно N раз включить-выключить. Номер работающего выключателя = количеству световых вспышек.
                                                                                                                                                                          0
                                                                                                                                                                          да, так даже сильно проще :)
                                                                                                                                                                            0
                                                                                                                                                                            Правильно :)
                                                                                                                                                                            0
                                                                                                                                                                            Мне кажется вариантов много, но, например, такой:

                                                                                                                                                                            1)
                                                                                                                                                                            Все выключатели выключены
                                                                                                                                                                            00000
                                                                                                                                                                            2)
                                                                                                                                                                            Включается пятый(1-й вариант)
                                                                                                                                                                            00001
                                                                                                                                                                            Выключаются все
                                                                                                                                                                            00000
                                                                                                                                                                            Делается два моргания лампочкой
                                                                                                                                                                            11111
                                                                                                                                                                            00000
                                                                                                                                                                            11111
                                                                                                                                                                            00000
                                                                                                                                                                            3)
                                                                                                                                                                            Вклчюается четвертый( 2-й вариант)
                                                                                                                                                                            00010
                                                                                                                                                                            Выключаются все
                                                                                                                                                                            00000
                                                                                                                                                                            Делается два моргания
                                                                                                                                                                            11111
                                                                                                                                                                            00000
                                                                                                                                                                            11111
                                                                                                                                                                            00000
                                                                                                                                                                            3)
                                                                                                                                                                            тоже самое с 00100

                                                                                                                                                                            Имеем — 5 промежутков — два моргания между каждым.
                                                                                                                                                                            Потом спрашиваем на какой раз было три( если вначале или в конце) или 5( если в середине) морганий подряд.

                                                                                                                                                                              0
                                                                                                                                                                              тут все просто: они договариваются о включении выключателей в определенное время и смотрят, когда лампа загорится.
                                                                                                                                                                                0
                                                                                                                                                                                часов нет )
                                                                                                                                                                                  0
                                                                                                                                                                                  Можно петь песенку :) Вместе (с) Гудзонский Ястреб.
                                                                                                                                                                                0
                                                                                                                                                                                  0
                                                                                                                                                                                  Теплота? Почему же это ответ?
                                                                                                                                                                                    0
                                                                                                                                                                                    оу, виноват, не вчитался ;)
                                                                                                                                                                                  0
                                                                                                                                                                                  В классике я слышал немного другие условия — 3 переключателя и 1 экспериментатор. Щелк первым на 5 секунд, выключили первый, щелк вторым и заходим — если теплая — значит 1, если горит — 2, если холодная и не горит — 3. Как-то так :)
                                                                                                                                                                                    0
                                                                                                                                                                                    Ну это уже другая задача. Со своим условием и спецификой.
                                                                                                                                                                                      0
                                                                                                                                                                                      Конечно — это ж детская задачка на сообразительность :)
                                                                                                                                                                                  0
                                                                                                                                                                                  зэки нумеруются от 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 попадет в камеру и застанет лампочку горящей, то можно утверждать что все тут уже побывали
                                                                                                                                                                                    0
                                                                                                                                                                                    уточнеие: зек может включить лампочку, если видел ее в предыдущий день включенной и его номер совпадает с номером текущего дня.
                                                                                                                                                                                    первый раз лампочку включит зек номер 1, попав в камеру в день с номером 1.

                                                                                                                                                                                    и там местами у меня написаны строгие равенства на месте нестрогих, сорри
                                                                                                                                                                                    –1
                                                                                                                                                                                    Вообще-то задача даже не подобная, а концептуально идентичная, не интересно.
                                                                                                                                                                                      +1
                                                                                                                                                                                      сначала зэки договариваются кто будет считать количество побывавших в камере с лампочкой.
                                                                                                                                                                                      далее алгоритм такой:
                                                                                                                                                                                      если зэк попал в камеру и лампочка выключена — он ее включает, а если она уже включена ждет следующего раза когда лампочка будет выключена.
                                                                                                                                                                                      зэк может включить лампочку только один раз.
                                                                                                                                                                                      главный зэк-счетовод выключает лампочку если она включена и увеличивает количество побывавших в камере на 1.
                                                                                                                                                                                        +1
                                                                                                                                                                                        Интерессено, если что такое «Высшая мера наказания»? Если смерть то Зэки бессмертные по условию задачи...:) В таком случае все зэки могут говорить нет, а тот который прйдет через сто дней скажет да, и все живые и здоровые пойдут в лес!:)
                                                                                                                                                                                          0
                                                                                                                                                                                          Эльфов убивали в фентезийных книгах. Головы рубили. Это он от старости умереть не могут.
                                                                                                                                                                                            0
                                                                                                                                                                                            да я же шучу) алгоритмическое решение нужно.
                                                                                                                                                                                          0
                                                                                                                                                                                          Сложно зайти плюсануть, откомментить и не прочесть другие коменты. Большое спасибо за задачку!
                                                                                                                                                                                            –5
                                                                                                                                                                                            Бред какой-то, а я думал вы взрослые и умные люди.
                                                                                                                                                                                          • UFO just landed and posted this here
                                                                                                                                                                                            • UFO just landed and posted this here
                                                                                                                                                                                                0
                                                                                                                                                                                                Пришёл к такому же мнению. Но есть проблема — по условию не дано начальное состояние лампочки. Если лампочка была изначально включена и в комнату зашёл «пахан», то он решил, что в комнате кто-то уже был и посчитает его, что может оказаться роковой ошибкой.
                                                                                                                                                                                                  0
                                                                                                                                                                                                  Уже поднимался вариант, что счетчиком становится тот, кого запустят в первый день. Тогда начальное состояние лампочки роли не играет.
                                                                                                                                                                                                  • UFO just landed and posted this here
                                                                                                                                                                                                0
                                                                                                                                                                                                Бит — но не двоичный. Лампочку можно нагревать и поворачивать на различный угол. ;)
                                                                                                                                                                                                  0
                                                                                                                                                                                                  Квантовый компьютер :true:
                                                                                                                                                                                                  0
                                                                                                                                                                                                  Задача нагло сперта отсюда =)
                                                                                                                                                                                                  Ну собственно там и решение есть.
                                                                                                                                                                                                    0
                                                                                                                                                                                                    мне больше нравится вариант, что она нагло сперта с университета Беркли. www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
                                                                                                                                                                                                    А решений есть штук 15
                                                                                                                                                                                                      0
                                                                                                                                                                                                      ну как знаешь =)
                                                                                                                                                                                                      Задача довольно популярная
                                                                                                                                                                                                      0
                                                                                                                                                                                                      Задача с Московской математической олимпиады 2003 года:
                                                                                                                                                                                                      olympiads.mccme.ru/mmo/2003/resh/9.htm
                                                                                                                                                                                                        0
                                                                                                                                                                                                        Ну вот, 3 источника уже нашли =)
                                                                                                                                                                                                        Да, кстати, на Эрудиторе прямо говорится, что задача с этой олимпиады
                                                                                                                                                                                                          0
                                                                                                                                                                                                          Ага, и на Хабре, что самое удивительное, она то же уже была habrahabr.ru/blogs/zadachki/11481/

                                                                                                                                                                                                          ЗЫ на той олимпиаде я ее решил =)))
                                                                                                                                                                                                          0
                                                                                                                                                                                                          Совсем нет, по ссылке задача много проще — там заключённым известно, что лампочка изначально выключена. Эта деталь крайне важна. Задача топикстартера же не решается вовсе. Объяснение нерешимости примерно такое — так как начальное состояние неизвестно, то, прочитав состояние лампочки, мы не сможем узнать, была ли передана какая-либо информация через неё или нет. А без передачи информации между узниками задача не решается.
                                                                                                                                                                                                            0
                                                                                                                                                                                                            Не важно, в каком состоянии первоначально была лампочка.
                                                                                                                                                                                                              0
                                                                                                                                                                                                              тут тоже можно сделать так, чтобы сааамый первый вошедший переводил лампу в известное всем состояние
                                                                                                                                                                                                            +2
                                                                                                                                                                                                            через 10 000 дней можно и так, любому желающему, сказать что все, баста, все уже побывали и с вероятностью в 99% быть освобожденным.

                                                                                                                                                                                                            (вероятность того, что каждый конкретный заключенный ни разу за 10 000 дней не побывает в камере = 0,01 процент, суммарно, для 100 заключенных = 1%)
                                                                                                                                                                                                              0
                                                                                                                                                                                                              c расчетами вы явно ошиблись. но мысль верная
                                                                                                                                                                                                            • UFO just landed and posted this here
                                                                                                                                                                                                                +1
                                                                                                                                                                                                                кстати можно чуть-чуть ускорить освобождение по методу «счетчика».

                                                                                                                                                                                                                1-й день: Первый зек включает лампочку, если она была выключена.
                                                                                                                                                                                                                2: Второй зек, если он не был в первый день, выключает лампочку.
                                                                                                                                                                                                                3: Третий зек, если он не был в первый и второй день включает лампочку, а становится «счетчиком» с +2, что потенциально сократит время пребывания в тюрьме на 100 или даже 200 дней.

                                                                                                                                                                                                                Если на третий день лампочка включена, или сам «счетчик» был два или три раза, то +2 не получилось, возвращаемся к плану «А» )
                                                                                                                                                                                                                • UFO just landed and posted this here
                                                                                                                                                                                                                    0
                                                                                                                                                                                                                    Еще, на основании этого способа, есть способ специально для людей, которые не живут вечно и понимают, что 30 лет никто из них не переживет:

                                                                                                                                                                                                                    1: зек_1 включает лампочку
                                                                                                                                                                                                                    2: зек_2 выключает лампочку, либо, если он был и в первый день, оставляет ее гореть.

                                                                                                                                                                                                                    далее, если лампочка «сбилась» каждый переключает ее в «неправильное» положение до 100-го дня.

                                                                                                                                                                                                                    Если на сотый день лампочка будет выключена (в «правильном» положении), значит каждый побывал в камере всего одни раз, и можно выходить на свободу. Если лампочка горит, значит кто-то был, как минимум, дважды. Все обнуляется, и запускаем алгоритм сначала.

                                                                                                                                                                                                                    Вероятность, к сожалению, просчитать не могу, но определенно какой-то шанс выйти уже на сотый день должен радовать душу заключенных, которые не хотят ждать 30 лет. А по истечении 30-ти летнего срока (10 000 дней) попробовать выйти с 99% вероятностью (см мой пост выше), что тоже неплохо.
                                                                                                                                                                                                                      0
                                                                                                                                                                                                                      Вероятность при таком подходе в 99 раз ниже, чем в варианте с 30 годами…
                                                                                                                                                                                                                        0
                                                                                                                                                                                                                        да, согласен. Наверное даже не в 99 раз, а гораздо больше. По крайне мере написанный алгоритм довел каунтер дней до 100 миллионов, так и не «выпустив узников».

                                                                                                                                                                                                                        Единственное, что в моем алгоритме смущает — каунтер не разу не поднялся выше 40-ка, хотя до этого порога доходит очень часто. Может быть это какое-то встроенное ограничение в rand().

                                                                                                                                                                                                                        может кто-то из программистов подскажет?
                                                                                                                                                                                                                          0
                                                                                                                                                                                                                          99 раз — примерная оценка для равномерного распределения. в общем случае будет больше. или меньше)

                                                                                                                                                                                                                          rand() выдает значения в пределах [0.0… 1.0], ну или [0… MAXINT]. если конечно не задано другое при вызове. 40 тут как-то ну совсем ни к чему. если хотя бы 42 было ;-)
                                                                                                                                                                                                                      +1
                                                                                                                                                                                                                      тут всего лишь 2 варианта гарантированого решения:
                                                                                                                                                                                                                      1. Есть счетчик как в примере по олимпиаде habrahabr.ru/blogs/zadachki/69558/#comment_1983026
                                                                                                                                                                                                                      2. Каждый раз в 100 дней побывает 1 раз в камере. (Каждый месяц выключать свет. Включать, если второй раз в камеру за 100 дней зашел)

                                                                                                                                                                                                                      Вероятности не считал.

                                                                                                                                                                                                                        0
                                                                                                                                                                                                                        2. За 100 дней в камере побывает каждый, ровно 1 раз. (Каждый 100-й день тушить лампочку, кто побывает 2й раз за 100 дней — лампочку включает)
                                                                                                                                                                                                                          0
                                                                                                                                                                                                                          не, есть еще одно гарантированное решение. Можно каждые 100 дней включать лампу.
                                                                                                                                                                                                                          В промежутке же ста дней выключать её, если зэк пошел второй или более раз.
                                                                                                                                                                                                                          Таким образом ждать момента, когда наступит стодневка, в которую каждый зек побывает в комнате единожды.

                                                                                                                                                                                                                          не криво объяснил?
                                                                                                                                                                                                                            0
                                                                                                                                                                                                                            ой, я ваше же решение и сказал. Пардон. Плюсик вам.
                                                                                                                                                                                                                            0
                                                                                                                                                                                                                            ох уж эти заумные мат. объяснения… «докажем от противного»… по моему проще понять, что каждый вошедший при «свободной» лампочке посылает сигнал счётчику, что он был, его можно засчитывать, а счётчик приняв сигнал опять освобождает лампочку. и так пока каждый не попадёт на «свободную» лампочку и не передаст сигнал.
                                                                                                                                                                                                                              0
                                                                                                                                                                                                                              Как именно вы пошлёте сигнал счётчику? Напомню, что по условию задачи начальное состояние лампочки неизвестно.
                                                                                                                                                                                                                                0
                                                                                                                                                                                                                                До того, как счётчик первый раз зашёл он и не считает.
                                                                                                                                                                                                                                Заходит первый раз — выключает лампу и начинает считать с единицы (себя).
                                                                                                                                                                                                                                А остальное много раз описано выше.
                                                                                                                                                                                                                                  0
                                                                                                                                                                                                                                  Тогда все зеки, зашедшие перед счетчиком, будут считать себя уже «посчитанными».
                                                                                                                                                                                                                                    0
                                                                                                                                                                                                                                    они договариваются, что первый зашедший включает лампочку, первый знает, что он первый т.к. зекам дают день на размышление, потом запускают в день по человеку. зажженая лампочка доходит до счётчика, он её выключает и ставит в своём блокноте 1 :) Зек запоминает что он уже включал и больше не включает и так далее…
                                                                                                                                                                                                                                  0
                                                                                                                                                                                                                                  Начальное состояние не важно: счетчик — зашедший в первый день. Теряем 1 день времени, но избавляемся от неопределенности состояния.
                                                                                                                                                                                                                                0
                                                                                                                                                                                                                                Я буду 99999-ым человеком, который решил задачу ) да еще крайне не оптимально. Зато простота реализации и понимания.

                                                                                                                                                                                                                                Решение

                                                                                                                                                                                                                                1 сентября выбирают зека-счетчика (ЗС). Зеки идут в камеры.

                                                                                                                                                                                                                                Игра начинается.Лампочку никто не трогает, пока не зайдет 3С.

                                                                                                                                                                                                                                • Заходит ЗС и включает лампочку.
                                                                                                                                                                                                                                • Все остальные, кто заходит в камеру с лампочкой, ее выключают, только если остальные заходят в первый раз. Включать лампочку остальным нельзя. Остальные говорят всегда начальнику «Нет».
                                                                                                                                                                                                                                • ЗС включает лампочку, если он была выключена. и ждет пока ее выключат 99 раз. Когда ЗС видит, что 99 раз ее уже выключили, ЗС говорит «Да».
                                                                                                                                                                                                                                  0
                                                                                                                                                                                                                                  Здесь нет вероятности. Сказать «Да» можно только честно.
                                                                                                                                                                                                                                  Здесь нет счета дней, так как зеки сидят в камерах без окон.
                                                                                                                                                                                                                                    0
                                                                                                                                                                                                                                    Ну такое решение уже раз 5 выше предлагалось. Правда с обратным действием включения-выключения.
                                                                                                                                                                                                                                      0
                                                                                                                                                                                                                                      Ничего страшного, что решение уже было! действия пользователя должны быть такими: прочитать, решить, похвастаться, получить плюсик!