Avito Cool Challenge 2018 |
---|
Закончено |
Это интерактивная задача.
Chouti устал от учебы, поэтому он открыл компьютер и стал играть в игру-головоломку.
Давным давно, Chouti нашел последовательность $$$s_1, s_2, \ldots, s_n$$$ длины $$$n$$$, хранимую коварным интерактором. Она состояла только из цифр $$$0$$$ и $$$1$$$, и количество цифр $$$1$$$ было равно $$$t$$$. Chouti ничего не знает о последовательности, кроме $$$n$$$ и $$$t$$$, но он может попробовать узнать последовательность с помощью интерактора.
Определим операцию инвертирования. Инвертирование отрезка $$$[l,r]$$$ ($$$1 \leq l \leq r \leq n$$$) означает, что для каждого $$$x \in [l,r]$$$, нужно заменить $$$s_x$$$ на $$$1-s_x$$$.
В каждом запросе Chouti может передать интерактору два числа $$$l,r$$$ удовлетворяющие $$$1 \leq l \leq r \leq n$$$ и интерактор сделает одно из двух: инвертирует отрезок $$$[1,r]$$$ или инвертирует отрезок $$$[l,n]$$$ (оба исхода равновероятны, и все решения, принимаемые интерактором, независимы друг от друга, см. Примечание ). Интерактор сообщит текущее количество цифр $$$1$$$ после каждой операции. Заметим, что последовательность не будет восстановлена после каждой операции.
Помогите мальчику найти изначальную последовательность за не более $$$10000$$$ запросов.
"Странная легенда, глупая игра.", — подумал он. Тем не менее, после нескольких попыток, он всё равно в неё играет. Можете ли вы ему помочь пройти эту игру?
Взаимодействие начинается со строки, содержащей числа $$$n$$$ и $$$t$$$ ($$$1 \leq n \leq 300$$$, $$$0 \leq t \leq n$$$) — длина строки и количество цифр $$$1$$$ в ней.
Далее вы можете совершать запросы.
Чтобы сделать запрос, выведите строку «? l r» ($$$1 \leq l \leq r \leq n$$$), и сбросьте буфер вывода.
После каждого запроса, считайте одно целое число $$$t$$$ ($$$-1 \leq t \leq n$$$).
Когда вы нашли начальную последовательность, выведите строку «! s», сбросьте буфер вывода и завершите вашу программу. Выводите $$$s_1, s_2, \ldots, s_n$$$ как двоичную строку и не выводите пробелы в промежутке между цифрами.
Ваше решение получит вердикт Решение «зависло», если вы ничего не выведете или забудете сбросить буфер вывода.
Чтобы сбросить буфер вывода вам нужно сделать следующее сразу после вывода запроса и символа конца строки:
Взломы
Для взломов используйте следующий формат:
В единственной строке выведите строку из нулей и единиц. Её длина будет равна $$$n$$$ и она будет воспринята как $$$s_1, s_2, \ldots, s_n$$$.
Например, файл теста из примера содержит строку «0011».
4 2
2
2
0
? 1 1
? 1 1
? 3 4
! 0011
Для первого запроса $$$1,1$$$, интерактор должен инвертировать $$$[1,1]$$$ или $$$[1,4]$$$. Он выбирает отрезок $$$[1,4]$$$, так что последовательность становится равна 1100.
Для второго запроса $$$1,1$$$, интерактор должен инвертировать $$$[1,1]$$$ или $$$[1,4]$$$. Он опять выбирает отрезок $$$[1,4]$$$, так что последовательность становится равна 0011.
Для третьего запроса $$$3,4$$$, интерактор должен инвертировать $$$[1,4]$$$ или $$$[3,4]$$$. Он выбирает отрезок $$$[3,4]$$$, так что последовательность становится равна 0000.
Q: Как интерактор выбирает между $$$[1,r]$$$ and $$$[l,n]$$$? Это действительно случайный выбор?
A: Интерактор использует секретный генератор псевдослучайных чисел. Только $$$s$$$ и ваши запросы будут хешированы и использованы как ключ для генератора. Поэтому, если вы используете одну и ту же последовательность запросов для одной и той же секретной строки, вы будете получать один и тот же результат. За исключением этого, вы можете считать решения действительно случайными, как подбрасывание идеальной монетки. Вам не нужно (и вы не должны) пользоваться тем, какой именно генератор используется, чтобы решить эту задачу.
Название |
---|