Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://codeforces.net/blog/entry/45307.
Вам дана строка $$$t$$$, состоящая из $$$n$$$ строчных латинских букв. Эта строка была получена следующим образом: сначала у жюри была строка $$$s$$$, состоящая также из $$$n$$$ строчных латинских букв. Затем к ней применили не более $$$n$$$ (возможно, ни одной) операций. $$$i$$$-я операция обозначается двумя целыми числами $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$), и означает обмен символов строки под номерами $$$a_i$$$ и $$$b_i$$$. Все операции были выполнены в том порядке, в котором они расположены в последовательности. Например, если $$$s$$$ — xyz, и было выполнено $$$2$$$ операции: $$$a_1 = 1, b_1 = 2$$$; $$$a_2 = 2, b_2 = 3$$$, то после первой операции текущая строка будет yxz, после второй — yzx, поэтому $$$t$$$ — yzx.
Ваше задание — восстановить исходную строку $$$s$$$. К сожалению, о последовательности операций вы ничего не знаете (вы даже не знаете, была ли в ней хотя бы одна операция). Но вы можете использовать ту же самую последовательность обменов на любой строке, на которой вы хотите, если в этой строке ровно $$$n$$$ символов, и все они — строчные латинские буквы. После применения последовательности операций на строке вы можете узнать, во что она превратилась.
Можете ли вы восстановить исходную строку $$$s$$$, использовав последовательность операций не более $$$3$$$ раз?
Строка $$$s$$$ и последовательность операций в каждом тесте являются фиксированными; интерактор не пытается адаптировать тест под ваше решение.
Изначально тестирующая система выводит одну строку $$$t$$$, состоящую из строчных латинских букв ($$$1 \le |t| = n \le 10^4$$$).
Чтобы дать ответ, ваша программа должна вывести одну строку $$$!$$$ $$$s$$$ с переводом строки в конце. После этого программа должна сбросить буфер вывода и завершиться.
До того, как ваша программа даст ответ, она может отправить не более $$$3$$$ запросов. Чтобы отправить запрос, выведите строку следующего формата: $$$?$$$ $$$s'$$$, где $$$s'$$$ должна быть строкой из ровно $$$n$$$ строчных латинских букв. Строка, которую вы отправляете, должна заканчиваться символов перевода строки. После отправки запроса программа должна сбросить буфер вывода и прочитать ответ на запрос — строку $$$t'$$$, состоящую из $$$n$$$ строчных латинских букв, которая будет являться результатом применения последовательности обменов к $$$s'$$$. Ответ будет дан на отдельной строке, заканчивающейся символом перевода строки.
Если вы зададите некорректный запрос (или же количество запросов превысит $$$3$$$), ответом будет строка 0. Если ваша программа получила такой ответ, она должна немедленно завершиться — иначе вы можете получить вердикт «Ошибка исполнения», «Превышено ограничение времени» или какой-нибудь другой, а не «Неправильный ответ».
yzx aab baa aba
? baa ? aba ? aab ! xyz
В примере рассматривается тест, который приводился в условии. Участник задает запрос со строкой baa, которая превращается в aab. Во втором запросе задается строка aba, которая превращается в baa. В третьем запросе задается строка aab, которая превращается в aba. Участник может понять, что изначально строка $$$s$$$ была xyz.
Замечание к фазе взломов:
Чтобы отправить тест в фазу взломов, предоставьте его в следующем виде:
В первой строке должна быть записана строка $$$s$$$, которую вы загадываете, состоящая из $$$n \in [1, 10000]$$$ строчных латинских букв.
Во второй строке должно быть записано одно целое число $$$k$$$ ($$$0 \le k \le n$$$) — количество операций в последовательности обменов.
Затем должны следовать $$$k$$$ строк, $$$i$$$-я из которых должна задавать $$$i$$$-ю операцию обмена двумя целыми числами $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$).
Например, тест из условия выглядел бы вот так:
xyz
2
1 2
2 3
Название |
---|