Тест теста

[Dendr]

Я не до конца поняла, откуда у тебя взялось 19... по моей грубой оценке получается 16... Правда это означает, что 14 все равно не проходит(((

19 - это очень грубо, конечно, но вот как я считал.
У нас всего 2^100 вариантов. После первого запроса "ддд...д" самый худший вариант - 50. Остается "всего" 100!/(50!)^2 (=10^29) вариантов. И мы теперь применяем несколько раз (пусть 17) подряд некие запросы, получая разные ответы. В лучшем случае у нас будет один из 50 вариантов ответа (потому что четность будет одна и та же!). То есть, в лучшем случае, мы сократим наше множество вариантов в 50^17 раз = (0.7*10^29).
Это значит, что есть по крайней мере несколько подгрупп размером 2. А это значит, что нужно обязательно применить еще один раз запрос. Итого 1+17+1=19. По-моему, так, не иначе. Быстрее в принципе нельзя, как ни изголяйся.

[Юляша]

Я не до конца поняла, откуда у тебя взялось 19... по моей грубой оценке получается 16... Правда это означает, что 14 все равно не проходит(((

19 - это очень грубо, конечно, но вот как я считал.
У нас всего 2^100 вариантов. После первого запроса "ддд...д" самый худший вариант - 50. Остается "всего" 100!/(50!)^2 (=10^29) вариантов. И мы теперь применяем несколько раз (пусть 17) подряд некие запросы, получая разные ответы. В лучшем случае у нас будет один из 50 вариантов ответа (потому что четность будет одна и та же!). То есть, в лучшем случае, мы сократим наше множество вариантов в 50^17 раз = (0.7*10^29).
Это значит, что есть по крайней мере несколько подгрупп размером 2. А это значит, что нужно обязательно применить еще один раз запрос. Итого 1+17+1=19. По-моему, так, не иначе. Быстрее в принципе нельзя, как ни изголяйся.

Да, все правильно... я считала так же, только плохо((((. Формула точно та же...

[dP]

Хм, если придумать стратегию, которая за k запросов отсеивает в n^k вариантов тестов, то она заведомо будет оптимальна...

[Юляша]

На всякий случай, до кучи - достаточно очевидный факт, может где-нить кому-нить поможет...

Если для X(1) существует решение в Y(1) прогонов, для X(2) - в Y(2), ... , для X(N) - в Y(N), то
для X(1)+X(2)+...+X(N) существует решение в Y(1)+Y(2)+...+Y(N) прогонов

[Dendr]

На всякий случай, до кучи - достаточно очевидный факт

Разве?
Берем 2 - 2 прогона и 3 - 3 прогона. 2+3=5, 2+3=5. Однако 5 решается и за 4 прогона. Хотя согласен - верхнюю границу так вроде можно оценить.

[Dendr]

Накатал в Маткаде программку для такого теста для N=8 и 16.
На 8 - это была проверка работоспособности. Как и требовалось - выдала, что после запросов дддддддд дддднннн и т.д. и выходном данном каждый раз 4, в итоге останется ровно 8 вариантов. Они, как уже показано, решаются за 2 доп.запроса.

На 16 - это уже был честный расчет, "вслепую". Аналогичные запросы (уже 5 штук) с выходом каждый раз 8 оставляют в итоге 222 (двести двадцать два) варианта. (Ожидалось теоретически около 250) Выписать их все, извините, не смогу... Ну вот некоторые: 4080, 13740, 23610, 29325, 36273, 58407. (чтобы увидеть ряд - переводим числа в двоичную запись и заменяем 1 на "да", 0 на "нет")

Остается открытым вопрос, за сколько ходов можно выделить ровно один вариант. Не меньше трех, понятно.

Ниже - полный бред, конечно. Можно и проверить, но это очень долгое время займет. И так для 16 расчет идет минут 5. Для 32 уже это займет как минимум сутки...
Очень эмпирически... и гипотетически - остаток растет "суперэкспоненциально", т.е. как ехр(ехр(х)): 4->2, 8->8, 16->222... Тогда 32->32^3, то есть 32 решится не менее, чем за 11 ходов (6+5). А для 128 - по этой же очень извращенной логике получается 27. Для 100, значит, где-то 23.

[Юляша]

Я тоже хочу попробовать с программой. Мне кажется, что метод "минимакса" (каждый раз выбираем попытку, оставляющий минимальное число возможных ответов на следующем прогоне, и дальше работаем именно с этими вариантами) должен давать результат близкий к оптимальному. Если получится - прогоню для всех четных чисел от 6 до 16.

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

[Юляша]

Ну вот и компьютерные чудеса)))

Прогнала все четные значения от 6 до 14
Думаю, что можно смело утверждать, что мы имеем оптимальные последовательности с точностью +-1 прогон. В каждой последовательности отсутствует первый вопрос ("все да" или "все нет") с ровно 50% правильных ответов.
Первое число - это заданный вопрос, второй - максимальное число остающихся вариантов, третье - результат теста. Кстати, набежала соответствующая дополнительная задача.

Вы - Петя. Вы прогнали заданные тесты с приведенными результатами.
Вот теперь вперед - пройдите тест со 100% правильных ответов



111000 9 2
110100 4 2
110000 2 1
000010 1 2


11100000 30 3
10011000 13 3
01010100 5 3
00110000 2 2
10000000 1 3


1111100000 100 4
1100010000 42 4
1100001100 15 5
1010011000 5 3
0110000000 2 3
0001000000 1 4


111110000000 350 5
110001110000 132 7
101001001100 47 5
101000110000 16 4
000100101000 6 5
000010100000 2 4
000000000010 1 5


11111110000000 1225 6
11110001110000 440 6
00001111000000 144 5
10001100101000 51 6
01101100011000 15 5
01101100100100 4 5
01001010100000 1 3