E. Бинарные строки это просто?
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Вам дана неизвестная бинарная строка $$$s$$$$$$^{\text{∗}}$$$ длины $$$n$$$. Функция $$$f(l, r)$$$ определяется как количество различных элементов в массиве $$$a$$$, полученном следующим образом:

  • Пусть $$$S$$$ — это подстрока $$$s_l s_{l+1} \ldots s_r$$$. Пусть $$$m$$$ — длина этой подстроки.
  • Изначально массив $$$a$$$ пуст.
  • Для $$$i$$$-го $$$(0 \le i \lt m)$$$ левого циклического сдвига$$$^{\text{†}}$$$ строки $$$S$$$ обозначим через $$$x_{i}$$$ количество инверсий$$$^{\text{‡}}$$$.
  • Для каждого $$$i$$$ такого, что $$$0 \le i \lt m$$$, добавьте в массив $$$a$$$ значение $$$x_{i} \mbox{ mod } m$$$, где $$$u \mbox{ mod } v$$$ обозначает остаток от деления $$$u$$$ на $$$v$$$.

Чтобы определить строку $$$s$$$, вы можете задавать вопросы. В каждом вопросе вы можете выбрать $$$2$$$ целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) и получить значение $$$f(l, r)$$$. Каждый запрос имеет стоимость $$$\dfrac{n}{r-l+1}$$$. Обратите внимание, что стоимость не обязана быть целым числом.

Вам нужно определить скрытую бинарную строку, так чтобы суммарная стоимость запросов не более $$$\mathbf{max(30,3\cdot n)}$$$. Вам разрешается сделать не более $$$\mathbf{2}$$$ попыток угадать строку.

$$$^{\text{∗}}$$$Бинарная строка содержит только символы $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Пусть дана бинарная строка $$$s \; = \; s_{1}s_{2}\cdots s_{n}$$$. Тогда $$$k$$$-й левый циклический сдвиг строки $$$s$$$ определяется как $$$t_{k} \; = \; s_{k+1}s_{k+2}\cdots s_{n}s_{1}s_{2}\cdots s_{k}$$$.

$$$^{\text{‡}}$$$Пусть дана строка $$$s \; = \; s_{1}s_{2}\cdots s_{n}$$$. Количество инверсий строки $$$s$$$ определяется как количество пар индексов $$$i,j \; (1 \le i \lt j \le n)$$$ таких, что $$$s_{i} \gt s_{j}$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 3000$$$) — длину неизвестной строки $$$s$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$.

Протокол взаимодействия

Чтобы задать вопрос, выведите строку в следующем формате (без кавычек):

  • «$$$\texttt{? l r}$$$» ($$$1 \leq l \leq r \leq n$$$)
Жюри вернёт целое число $$$f(l, r)$$$.

Чтобы угадать строку $$$s$$$ (длина $$$s$$$ должна быть равна $$$n$$$), выведите одну строку в следующем формате (без кавычек):

  • «$$$\texttt{! s}$$$»
Жюри вернёт 1, если ответ верный, или 0, если ответ неверный.

Попытка угадать строку не считается запросом.

После этого, если ваша строка верна, переходите к следующему набору входных данных или завершите программу, если это был последний набор входных данных.

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

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Взломы

Чтобы сделать взлом, используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных должна содержать $$$n$$$ ($$$2 \le n \le 3000$$$) — длину строки $$$s$$$.

Вторая строка каждого набора входных данных должна содержать $$$s$$$ — бинарную строку длины $$$n$$$.

Сумма $$$n$$$ по всем наборам входных данных не должна превосходить $$$3000$$$.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
3
5

1

1

1

1
3

3

0

1
8

0

1
Выходные данные


? 1 5

? 2 5

? 3 5

! 00000


? 1 3

! 100

! 001


! 00000000

! 10101010
Примечание

В примере взаимодействия входные и выходные данные содержат пустые строки, чтобы выровнять ответы интерактора с запросами. Эти пустые строки не присутствуют в реальных входных и выходных данных.

В первом наборе входных данных скрытая строка равна $$$s =$$$ 00000. Здесь, поскольку 0 не может образовать ни одной инверсии, массив $$$a$$$ всегда будет равен $$$[0]$$$ для всех подстрок. Следовательно, $$$f(l, r)$$$ возвращает $$$1$$$ для всех запросов.

Здесь мы сделали $$$3$$$ запроса.

Первый запрос — это $$$f(1,5)$$$, он возвращает 1 — стоимость этого запроса равна $$$\dfrac{5}{5-1+1} = 1$$$.

Второй запрос — это $$$f(2,5)$$$, он возвращает 1 — стоимость этого запроса равна $$$\dfrac{5}{5-2+1} = \dfrac{5}{4}$$$.

Третий запрос — это $$$f(3,5)$$$, он возвращает 1 — стоимость этого запроса равна $$$\dfrac{5}{5-3+1} = \dfrac{5}{3}$$$.

Суммарная стоимость после всех этих запросов $$$ = 1 + \dfrac{5}{4} + \dfrac{5}{3} = \dfrac{47}{12}$$$, что меньше, чем $$$\max(30, 3\cdot n) = 30$$$.

После этого мы угадываем $$$s =$$$ 00000, на что интерактор возвращает $$$1$$$, указывая на правильность ответа. Затем мы переходим к следующему набору входных данных.

Во втором наборе входных данных скрытая строка равна $$$s =$$$ 001.

Мы делаем запрос $$$f(1,3)$$$, который возвращает 3. Стоимость этого запроса равна $$$\dfrac{3}{3-1+1} = 1$$$.

Суммарная стоимость запросов равна $$$1$$$, что меньше, чем $$$\max(30, 3\cdot n) = 30$$$.

Затем мы угадываем 100, на что интерактор возвращает 0, указывая, что ответ неверный.

Мы угадываем 001, на что интерактор возвращает 1, указывая, что ответ верный. Затем мы переходим к следующему набору входных данных.

Для третьего набора входных данных скрытая строка равна $$$s = $$$ 10101010.