roboforum.ru

Digit писал(а):А! Понял Я там не корректно написал.

Именно и не в 1 месте

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

Не проходит, тогда последовательности 1 2 3 и 1 3 4 тоже обе дадут 1 на выходе.

Digit писал(а):с 1 по 11 день все также, как в способе №2.
с 12 дня включительно заключенные телек не трогают.
если на 20-й день телек работал, то косяк. А если на протяжении второго десятка дней телек был выключен, значит посмотрели все.

Вот это вроде правильное решение, ну или будем считать что правильно, остальное мелочи, давай я его короче сформулирую для всех:

1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 10 день если № заключенного не совпал с № дня - заключенный выключает телевизор;
3. С 11 по 20 день телевизор не трогают;
4. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Теперь вопрос - есть ли алгоритм приводящий к правильном определению, были ли все, с большей вероятностью?

Добавлено спустя 5 минут 27 секунд:
Ну и можно ли доказать, что не существует более оптимального алгоритма

Добавлено спустя 5 минут 53 секунды:
По сути поведение каждого заключенного в каждый день представляется 2 битами - что он сделает если увидит состояние телевизор 0 и если увидит состояние телевизора 1.

Итого всего алгоритмов может быть - (2^2)^(10*20)=2^400, - есть где порыться

=DeaD= писал(а):давай я его короче сформулирую для всех:

1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 10 день если № заключенного не совпал с № дня - заключенный выключает телевизор;
3. С 11 по 20 день телевизор не трогают;
4. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Теперь вопрос - есть ли алгоритм приводящий к правильном определению, были ли все, с большей вероятностью?

Есть
Ты сформулировал мой первый алгоритм с доработкой из моего последнего поста. Но есть и мой алгоритм №2. В твоем стиле он напишется так:
1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 10 день если заключенный бывал уже у телика - он выключает телевизор;
3. С 11 по 20 день телевизор не трогают;
4. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Digit писал(а):1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 10 день если заключенный бывал уже у телика - он выключает телевизор;
3. С 11 по 20 день телевизор не трогают;
4. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Зачот! а еще быстрее выйти на свободу?

Пока вероятность срабатывания алгоритма 10!/10^10 ~= 0,036%

А вероятность, что побывают все сама по себе - сейчас прикину

Добавлено спустя 48 секунд:
PS: Digit, а ты в детстве не участвовал во всяких олимпиадах математических?

Добавлено спустя 12 минут 40 секунд:
Подсчет реальной вероятности, что все побывают в комнате минимум по 1 разу за 20 дней:
Всего исходов: 10^20.

Будем кодировать 2 уровнями возможные случаи, сгруппировав их в классы.

К одному классу будем относить варианты, когда заключенные с одинаковыми номерами побывали в комнате с телевизором одинаковое число раз. Сумма этих раз которые все побывали в той комнате, понятное дело, 20.

Понятно что размер класса в котором заключенные 1..10 побывали в комнате с телевизором N1..N10 раз есть 20!/(N1!*N2!*...*N10!).

Теперь нам надо быстро перебрать эти классы, чтобы сложить их размеры, для этого мы будем перебирать комбинации 10 чисел, таких, что каждая из них минимум единица и в сумме будет 20, что эквивалентно комбинациям 10 чисел, каждое из них минимум 0 и в сумме будет 10. А таких комбинаций у нас 19!/(10!*9!)=92378

Чего-то тут надо программку писать уже

Добавлено спустя 1 минуту 6 секунд:
2Digit: Кстати, а что если такой алгоритм:

1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 20 день если заключенный бывал уже у телика 2 раза - он выключает телевизор;
3. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Он лучше или нет?

Dead, у меня от твоих выкладок моск вскипел
На олимпиадах математических был несколько раз в детстве, но безрезультатно

=DeaD= писал(а):2Digit: Кстати, а что если такой алгоритм:

1. Заключенный приходящий в первый день инициализирует телевизор включая его, далее действует как и в другие дни (см. пункт 2);
2. С 1 по 20 день если заключенный бывал уже у телика 2 раза - он выключает телевизор;
3. Если в конце телевизор включен - значит 100% побывали все, иначе неизвестно.

Он лучше или нет?

Я так понимаю, что на третий заход заключенного он вырубает, да?
Лучше ли... ХЗ Либо такой же, либо лучше (точно не хуже). Мне кажется, что лучше. Но посчитать я не осилю

Вероятность этого алгоритма (когда на 3-й заход вырубает): 20!/(2^10)/10^20=0.0023%, вот! посчитал!

так что хуже оно...

Добавлено спустя 39 секунд:

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

Оч странно неправильные олимпиады?

=DeaD= писал(а):Оч странно неправильные олимпиады?

просто у нас в стране много талантливых одаренных детей

Добавлено спустя 46 секунд:

=DeaD= писал(а):Вероятность этого алгоритма (когда на 3-й заход вырубает): 20!/(2^10)/10^20=0.0023%, вот! посчитал!

так что хуже оно...

Мдя...
Ну тогда думаем дальше

Я знаю решение, когда количество дней значительно больше количества заключенных:
1. Выбирается один заключенный - наблюдатель (Н).
2. Все остальные, когда заходят первый раз - включают телек. В остальные разы не трогают его.
3. Н каждый раз когда видит включенный телек - выключает его.
4. Как только Н выключит телек 19 раз - он докладывает, что все его посмотрели.

Я пытаюсь адаптировать этот алгоритм к 20 дням, но не получается. Может в условиях ошибка? Например, следует ли считать все визиты к телеку с первого дня или только визиты с начала 20-дневного периода?

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

Digit писал(а):просто у нас в стране много талантливых одаренных детей

Не настолько а ты на какого уровня олимпиадах был?

Добавлено спустя 3 минуты 11 секунд:

RiO писал(а):Я знаю решение, когда количество дней значительно больше количества заключенных:
1. Выбирается один заключенный - наблюдатель (Н).
2. Все остальные, когда заходят первый раз - включают телек. В остальные разы не трогают его.
3. Н каждый раз когда видит включенный телек - выключает его.
4. Как только Н выключит телек 19 раз - он докладывает, что все его посмотрели.

Не понял, а где тут гарантия, что заключенный #X был 100% в комнате? Вы их так до казни доведёте

Добавлено спустя 38 секунд:

Digit писал(а):В общем, это решение другой задачи

Это не решение - где гарантия что все посмотрели, когда Н это объявил?

Добавлено спустя 3 минуты 10 секунд:
А вообще хороший вопрос - есть ли более эффективный алгоритм для 100 или 1000 дней и 10 заключенных?

=DeaD= писал(а):а ты на какого уровня олимпиадах был?

на краевых

=DeaD= писал(а):

RiO писал(а):Я знаю решение, когда количество дней значительно больше количества заключенных:
1. Выбирается один заключенный - наблюдатель (Н).
2. Все остальные, когда заходят первый раз - включают телек. В остальные разы не трогают его.
3. Н каждый раз когда видит включенный телек - выключает его.
4. Как только Н выключит телек 19 раз - он докладывает, что все его посмотрели.

Не понял, а где тут гарантия, что заключенный #X был 100% в комнате? Вы их так до казни доведёте

на самом деле косяк не в отсутствии гарантии, а в том, что есть великий шанс, что Н не дождется 9 включений, т.к. при текущем описании алгоритма при попадении первый раз к ТВ заключенных №3, №8 и Н, последний зафиксирует только 1 включение, тогда как включалось по факту 2 раза и заключенный №8 больше включать телек не будет.

=DeaD= писал(а):А вообще хороший вопрос - есть ли более эффективный алгоритм для 100 или 1000 дней и 10 заключенных?

Мне кажется, что для больших промежутков времени и условия, что любой заключенный в любой день может объявить о том, что "все готово", алгоритм Рио с некоторыми доработками будет оптимальнее, чем тупое ожидание определенной комбинации, как в алгоритмах для 20 дней.

а вообще, что-то мне это все напоминает теорию кодирования и передачи сигналов

=DeaD= писал(а):Не понял, а где тут гарантия, что заключенный #X был 100% в комнате? Вы их так до казни доведёте

Если не был, то Н выключит телек только 18 раз.

Может уже автор поделится ответом для 20 дней?

Rio, а что насчет моих мыслей, которые я привел выше, о твоем алгоритме?

2RiO: Не катит так. Вот если модифицировать чуть решение:

1. Выбирается заключенный "наблюдатель" (далее Н);
2. Заключенный пришедший в первый день инициализирует телевизор выключая его, а дальше действует как все, как будто только пришел;
3. Каждый заключенный кроме Н если попадает в комнату с выключенным телевизором и еще ни разу не переводил его в состояние ВКЛ, включает его;
4. Если Н видит включенный телевизор, он выключает его;
5. Если Н выключил телевизор 9 раз - значит все побывали уже.

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

Добавлено спустя 57 секунд:

RiO писал(а):Может уже автор поделится ответом для 20 дней?

Ответ для 20 дней известен мне в 2 вариантах - когда заключенные только по своему номеру и дням называют и путём исключения 2-го посещения в первые 10 дней, в общем оба решения Digit'a.

Digit писал(а):на самом деле косяк не в отсутствии гарантии, а в том, что есть великий шанс, что Н не дождется 9 включений, т.к. при текущем описании алгоритма при попадении первый раз к ТВ заключенных №3, №8 и Н, последний зафиксирует только 1 включение, тогда как включалось по факту 2 раза и заключенный №8 больше включать телек не будет.

Действительно, в этом случае требуется поправка DeaDa (спасибо ему) . #8 должен дождаться пока увидит выключенный телек и таки включить его.