Codeforces Round 614 (Div. 1) |
---|
Закончено |
Это интерактивная задача!
Это был обычный день в тайном офисе в A.R.C. Markland-N, когда капитан-исследователь Сагар передал Рин необычный артефакт.
После некоторого анализа, Рин поняла, что этот артефакт содержит информацию о странном цветке, который существовал задолго до нашей эры. Однако информация о химической структуре цветка оказалась зашифрованной.
Химическая структура цветка может быть представлена как строка $$$p$$$. Исходя из незашифрованных бумаг рядом, Рин выяснила, длину строки $$$n$$$ и что эта строка может содержать только следующие три буквы: «C» (углерод), «H» (водород), и «O» (кислород).
В каждый момент Рин может ввести строку $$$s$$$ произвольной длины в специальный терминал артефакт, и он в ответ выведет все возможные начальные позиции вхождения $$$s$$$ как подстроки в $$$p$$$.
Тем не менее, запас энергии артефакта достаточно ограничен, и артефакт нельзя перезарядить, так как его технология слишком несовременная и несовместима ни с одним устройством A.R.C. Более точно:
Артефакт очень ценен, но и столь же хрупок. Рин очень боится повредить артефакт навсегда в попытках извлечь данные. Не могли бы вы ей помочь?
Взаимодействие начинается с целого числа $$$t$$$ ($$$1 \le t \le 500$$$), количества тестовых случаев. Взаимодействие для каждого тестового случая описано ниже:
Сначала вам нужно считать целое число $$$n$$$ ($$$4 \le n \le 50$$$), длину строки $$$p$$$.
После этого вы можете делать запросы вида «? s» ($$$1 \le |s| \le n$$$), чтобы найти вхождения $$$s$$$ в $$$p$$$.
После запроса, вам нужно считать ответ на него как последовательность целых чисел в одной строке:
Когда вы выясните строку $$$p$$$ выведите «! $$$p$$$» чтобы завершить текущий тестовый случай. Это действие не тратит энергию. Интерактор в ответ вернёт $$$1$$$ или $$$0$$$. Если интерактор вернул $$$1$$$, то вы можете начать обрабатывать следующий тестовый случай, если он есть, или завершить программу, если это был последний тестовый случай.
Если интерактор вернул $$$0$$$, то это означает что ваше предположение некорректно и вы должны немедленно завершить программу, чтобы гарантировать вердикт «Неправильный ответ».
Обратите внимание что в каждом тестовом случае строка $$$p$$$ зафиксирована заранее и не меняется в зависимости от запросов, иначе говоря, интерактор не адаптивен.
После вывода любого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы можете получить вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Для взломов используйте следующий формат:
Первая строка должна содержать целое число $$$t$$$ ($$$t = 1$$$).
Вторая строка строка должна содержит целое число $$$n$$$ ($$$4 \le n \le 50$$$) — длину строки.
Вторая строка должна содержать строку длины $$$n$$$, состоящую только из символов «C», «H» и «O». Эта та строка, которую взламываемому решению придётся угадать.
1 4 2 1 2 1 2 0 1
? C ? CH ? CCHO ! CCHH
2 5 0 2 2 3 1 8 1 5 1 5 1 3 2 1 2 1
? O ? HHH ! CHHHH ? COO ? COOH ? HCCOO ? HH ! HHHCCOOH
Обратите внимание что в примере взаимодействия есть лишние пустые строки для удобства чтения.
В реальном взаимодействия таких строк нет, и ваша программа тоже не должна их выводить.
Название |
---|