Реши задачку, используя один бит памяти 2: учитываем помехи

День эльфов на Хабре. :)
А по теме: прошлые зэки тоже выбирались случайно, а еще может стоит вернуть повторения? Так будет еще сложнее. :)

собственно вот мое решение предыдущей задачи, модифицированное для новых условий

зэки нумеруются от 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)
или
б) он видел ее включенной в предыдущий день и сегодня его день (z(Z) >= D — 1 && Z == D)

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

PS: ох и долго ж им там сидеть придется :(

Внимание нас N тысяч и нам реально нехуй делать [x]
N мало возьмем M [x]
Пост доказывающий превосходство хабрахабра над другими жалкими IT блогами [x]
Вернусь завтра и досчитаю [x]

извините, вырвалось…

математичное решение прошлой задачи, вроде, подходит и тут тоже.
Напомню — делим вечность, отведенную эльфам на куски по 100*100 дней. И теперь ээльфы считают:
если лампа включена в период 1-100 или 10 000 — 10 100 или 20 000 — 20 100, и т.д. значит зашел первый, ибо только он имеет право включить лампу в этот день.
если лампа включена в период 101-200 или 10 101 — 10 200 или 20 101 — 20 200 ит.д, значит зашел второй.
и т.д.
Каждыйзашедший в указанные периоды будет ставить галочки на своём листке папируса и когда все пройдут — каждый скажет об этом тюремщику.

есть ли более умное решение?

Пусть каждый зек, который заходит первый раз выкручивает и разбивает лампочку :) Охранник будет менять лампочки, следовательно каждый раз лампочка будет новая и в состоянии выкл.
100 разбитых лампочек = свобода :)

Я один думаю, что они никогда не выйдут?))
Просто если их водят случайно и с повторениями, то существует ненулевая вероятность того, что есть эльфы, которые никогда не попадут в комнату

Наиболее оптимальный вариант поведения в столь плачевной ситуации. Первый эльф кому посчастливится побывать в комнате 100 раз, говорит да.

Один из эльфов может объявить себя мессией и проповедовать другим убить себя

Было у меня к прошлому решение, оно подходит и тут вроде по всем пунктам ужесточений. Правда при симуляции по старым правилам выходило 80-100 тысяч дней вместо 10 по другому решению. но всё же решение абсолютно стопроцентное.

вот решение по предыдущему варианту:
gist.github.com/186961

Для нового варианта нужно небольшой патч на проверку:

— if zek.table.all? {|x| x == true}
+ if zeks.all? {|z| z.table.all? {|x| x}}

Допущение что у каждого зека эльфа достаточно хорошая память чтобы запоминать 100 бит информации. (Я думаю это можно организовать договорись первые 100-500 дней тренеровать память, а потом начинать действовать =) )

Итак алгоритм:
Каждому зеку присваивается номер от 0 до 99 (можно от 1 до 100 не важно).
Все дни тоже нумеруются от 0 до 99 циклично. (выключение света на это не влияет, ведь время не перестаёт идти).
Если зэк приходит в день который совпадает с его номером то он включает лампочку.

Теперь интереснее.

Если зэк приходит и видит включенную лампочку, то значит зэк с номером на 1 меньше чем номер текущего дня (с учётом цикличности) точно посещал камеру, у зэка в памяти есть табличка где он записывает: ага, зэк 30 был тут. Этот зек, у которого в табличке уже отмечена 2 зека (он и зэк из прошлого дня) будет включать лампочку и в свой день и день зэка предыдущего дня.

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

Всё таки переписал симуляцию, только она очень медленно работает на последних итерация, но оптимизировать уже нет сил.
Прогнал одну симуляцию вышло 237009 дней, всего то 649 лет, что это может значить для эльфа. Симуляция учитывает что в 40% случаев случиться что-то плохое, охранник выключит свет, или ещё что. Вот код:

gist.github.com/186973

Теперь почему мой алгоритм учитывает все 5 усложнений:

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

2. Горение лампы может прерываться охранником либо перебоями в электричестве (лампочка выключается сама по себе).
Если зэк не учёл послание предыдущего ничего страшного, неверные данные никуда не пойдут.

3. Походы могут быть не каждый день (из-за отключения электричества).
Но время течёт всё равно в своём порядке 10 день будет 10 по расчётам зеков а 10130 — 30.

4. Ответ должен держать не один, а все.

Все заполняют таблички до конца.

5. Эти эльфы терпеливей, ждать им придётся дольше, бедняжкам.

650 лет) Но думаю есть решения и быстрее.

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

Вопрос: как, с учетом непредсказуемой величины помех (насколько последователен охранник?), оптимальнее определить длину периода:

1) фиксированный период (1, 100 или какое угодно число дней);
2) линейное увеличение 1-2-3-4...;
3) экспоненциальное увеличение 1-2-4-8...;
4) НЛО его знает?

Ситуация представляет собой дилемму «время ожидания vs. охват периода». Если тасовать зеков по одному, каждый сможет передать информацию максимум одному следующему зеку. Если растянуть период, скажем, до 100 дней, чтобы зек имел больше вероятности попасть в свой период (но она никогда не достигнет 1!), то один лишь случай пунктуальности охранника способен сделать дальнейшее ожидание бесполезным. Первое, что приходит в голову (и что вероятнее всего придет в голову зекам за не слишком продолжительное время обеда) — среднее геометрическое между этими крайностями — 10. Подозреваю, что самая оптимальная величина рассчитывается с использованием числа е, типа ln (100) или что-то вроде этого.

а на двери камеры, одного из эльфов, мелом написано:«этого в комнату не водить!»

Лучше бы сделали задачу с 2мя лампочками и целью максимально оптимизировать процесс. =)

Выкручиваем лампочку, так чтобы она не включалась.
Переключатель включения лампы — 0 или 1
Зек когда входит — вкручивает лампочку, проверяет горит или нет :)

Нумеруем дни 0-100, каждому эеку даем номер 0-100
Если зек пришел в день со своим номером — вкручивает лампочку.
Если пришел не в свой день, проверяет лампочку (горит или нет), заносит себе в блокнот кто уже побывал в комнате :)

> заходят в комнату, эльф садится, включает лампу, рисует, либо читает книгу, либо думает, либо делает что-либо еще

Если их рисунки никто не «удаляет» — никаких проблем идентификации не вижу :).