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