Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 45
День эльфов на Хабре. :)
А по теме: прошлые зэки тоже выбирались случайно, а еще может стоит вернуть повторения? Так будет еще сложнее. :)
А по теме: прошлые зэки тоже выбирались случайно, а еще может стоит вернуть повторения? Так будет еще сложнее. :)
собственно вот мое решение предыдущей задачи, модифицированное для новых условий
зэки нумеруются от 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: ох и долго ж им там сидеть придется :(
зэки нумеруются от 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: ох и долго ж им там сидеть придется :(
Что-то я не понял, кто включает лампочку в первый раз. Из условий (а) и (б) выходит, вроде, что никто.
«ох и долго ж им там сидеть придется».
«ох и долго ж им там сидеть придется».
У меня почти также. Но вот это Ваше
даст эльфам пару лишних сотен лет на свободе (если не тысяч), по сравнению с моим решением.
если лампочка не горит, то зек включает ее, если:
а) если он уже видел ее включенную в этот день (z(Z) >= D)
даст эльфам пару лишних сотен лет на свободе (если не тысяч), по сравнению с моим решением.
Похоже на мой алгоритм (описанный ниже), но не пойму эффективней или нет, вы не делали симуляцию? интересно было бы сравнить время.
Внимание нас N тысяч и нам реально нехуй делать [x]
N мало возьмем M [x]
Пост доказывающий превосходство хабрахабра над другими жалкими IT блогами [x]
Вернусь завтра и досчитаю [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 дней. И теперь ээльфы считают:
если лампа включена в период 1-100 или 10 000 — 10 100 или 20 000 — 20 100, и т.д. значит зашел первый, ибо только он имеет право включить лампу в этот день.
если лампа включена в период 101-200 или 10 101 — 10 200 или 20 101 — 20 200 ит.д, значит зашел второй.
и т.д.
Каждыйзашедший в указанные периоды будет ставить галочки на своём листке папируса и когда все пройдут — каждый скажет об этом тюремщику.
есть ли более умное решение?
На самом деле тут очень хорошо подходит вариант с периодом (каждому зеку по 100 дней на включение лампочки) и дополнительная фича, что включать лампочку в этот период может не только зек, который к этому периоду привязан, но и зек, который уже знает, что тот зек там был (видел лампочку зажженой ранее). Т.е. получается социальная система, чем больше зеки узнают о других зеках, которые были в комнате, тем чаще они это знание распространяют, и становится неважно, что лампочка иногда гаснет.
Пусть ногтями на стене шкрябают 100 царапинок :)
Пусть каждый зек, который заходит первый раз выкручивает и разбивает лампочку :) Охранник будет менять лампочки, следовательно каждый раз лампочка будет новая и в состоянии выкл.
100 разбитых лампочек = свобода :)
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 лет) Но думаю есть решения и быстрее.
вот решение по предыдущему варианту:
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) или что-то вроде этого.
Вопрос: как, с учетом непредсказуемой величины помех (насколько последователен охранник?), оптимальнее определить длину периода:
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
Если зек пришел в день со своим номером — вкручивает лампочку.
Если пришел не в свой день, проверяет лампочку (горит или нет), заносит себе в блокнот кто уже побывал в комнате :)
Переключатель включения лампы — 0 или 1
Зек когда входит — вкручивает лампочку, проверяет горит или нет :)
Нумеруем дни 0-100, каждому эеку даем номер 0-100
Если зек пришел в день со своим номером — вкручивает лампочку.
Если пришел не в свой день, проверяет лампочку (горит или нет), заносит себе в блокнот кто уже побывал в комнате :)
А обязательно ли считать по лампочкам?
Вот к примеру, эльфы имеют волосы, можно что бы каждый эльф который посешает в первые комнату оставлял 1-ну волосинку ( ну есть куча вариантов что осавлять, ногти или если у них такойже как у людей пишеварительный тракт, то они могут наложить 100 кучек (; ) Вобшем исходя из физиологии можно оставлять часть эльфа и когда насобирается 100 частей все они могут смело начать говорить да (;
Вариант читерский, но нигде ж не написано что комнату будут убирать или что эльфам запрешено что то оставлять после себя (;
Вот к примеру, эльфы имеют волосы, можно что бы каждый эльф который посешает в первые комнату оставлял 1-ну волосинку ( ну есть куча вариантов что осавлять, ногти или если у них такойже как у людей пишеварительный тракт, то они могут наложить 100 кучек (; ) Вобшем исходя из физиологии можно оставлять часть эльфа и когда насобирается 100 частей все они могут смело начать говорить да (;
Вариант читерский, но нигде ж не написано что комнату будут убирать или что эльфам запрешено что то оставлять после себя (;
А еше не совсем понятно про книжку и рисунки.
Допустим 1-н альбом на всех эльфов и 1 книжка на всех эльфов.
Тода допустим все они захотят прочитать «Войну и мир» и те эльфы которые попадают в камеру впервые заламывают 1-н уголок страници, если они уже были то соответственно ничего. Когда на 100 стр. будет зогнутый уголок начиная с этого времени они все могут начать говорить «Да»
Насчет альбома, который один на всех, допустим когда в первые попадает в комнату рисует рисунок начного времени суток, все последующие разы — утро, когда насобирается 100 ночей, начинаем говорить «Да»
Допустим 1-н альбом на всех эльфов и 1 книжка на всех эльфов.
Тода допустим все они захотят прочитать «Войну и мир» и те эльфы которые попадают в камеру впервые заламывают 1-н уголок страници, если они уже были то соответственно ничего. Когда на 100 стр. будет зогнутый уголок начиная с этого времени они все могут начать говорить «Да»
Насчет альбома, который один на всех, допустим когда в первые попадает в комнату рисует рисунок начного времени суток, все последующие разы — утро, когда насобирается 100 ночей, начинаем говорить «Да»
Еше решение с лампой, допустим есть все тот же эльфо-счетовод,
Когда эльф впервые попадает в комнату он ставит лампу с правой стороны стола.
Только счетовод имеет право ставить лампу на левую сторону, и он её выключает!
После того как счетчик дойдет до 99 счетовод говорит «Да» и оставляет лампу включенной, и каждый раз когда его будут приводить в комнату он будет оставлять ее слевой стороны стола включенной.
Как только зек видет включенную лампу с левой стороны стола, он начинает говорить «Да» и тоже оставлять все время включенный свет. И так до тех пор пока все 100 не скажут «Да»
Когда эльф впервые попадает в комнату он ставит лампу с правой стороны стола.
Только счетовод имеет право ставить лампу на левую сторону, и он её выключает!
После того как счетчик дойдет до 99 счетовод говорит «Да» и оставляет лампу включенной, и каждый раз когда его будут приводить в комнату он будет оставлять ее слевой стороны стола включенной.
Как только зек видет включенную лампу с левой стороны стола, он начинает говорить «Да» и тоже оставлять все время включенный свет. И так до тех пор пока все 100 не скажут «Да»
> заходят в комнату, эльф садится, включает лампу, рисует, либо читает книгу, либо думает, либо делает что-либо еще
Если их рисунки никто не «удаляет» — никаких проблем идентификации не вижу :).
Если их рисунки никто не «удаляет» — никаких проблем идентификации не вижу :).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реши задачку, используя один бит памяти 2: учитываем помехи