Задача №115247. Строчечка
Это интерактивная задача.
Программа жюри загадала строку \(s\) длины \(n\), которая состоит из букв « a », « b » и « c ». Ваша программа должна её угадать.
Чтобы угадать строку, ваша программа может делать запросы. Каждый запрос представляет собой число \(i\) (\(1 \le i \le n - 1\)) и строку \(u\) длины два, состоящую из строчных букв английского алфавита. В ответ на запрос программа жюри сообщает, сколько из утверждений \(s_i = u_1\) и \(s_{i+1}=u_2\) верны.
Требуется угадать загаданную строку, сделав не больше \(\lceil \frac43 n \rceil\) запросов. Здесь \(\lceil \ldots\rceil\) означает округление вверх.
В этой задаче вам надо будет несколько раз сыграть с программой жюри. Гарантируется, что количество игр в каждом запуске не превышает \(100\).
В начале каждой игры ваша программа должна считать со стандартного потока ввода число \(n\) (\(2 \le n \le 100\)). Если \(n=0\), то это значит, что ваша программа должна завершить свое исполнение. В ином случае вы начинаете игру с загаданной строкой длины \(n\), и ваша программа может выполнить не более \(\lceil \frac43 n \rceil\) запросов.
Чтобы сделать запрос, необходимо вывести в поток вывода « ? \(i\) \(u\) », где \(1 \le i \le n - 1\), \(u\) — строка длины два из строчных английских букв. В ответ необходимо считать из стандартного потока ввода целое число \(a\), равное 0, 1 или 2 — сколько утверждений из \(s_i = u_1\) и \(s_{i+1}=u_2\) верны.
Когда ваша программа угадала загаданную строку, необходимо вывести в стандартный поток вывода « ! \(s\) », где \(s\) — строка длины \(n\), которую загадала программа жюри. Вывод ответа не считается запросом. После того, как ваша программа выведет угаданную строку, она сразу же может приступать к следующей игре.
Программа жюри в этой задаче может быть адаптивной. Иначе говоря, программа жюри может подбирать свои ответы таким образом, что существует строка, для которой все ответы корректны, но она не фиксирована заранее, а меняется в зависимости от запросов вашей программы. В частности, если существует строка, для которой все ответы на запросы являются корректными, но отличная от строки, которую угадала ваша программа, решение может получить вердикт «Wrong answer».
3
2
1
1
2
0
? 1 ab
? 2 ba
? 2 bb
? 2 bc
! abc
В примере интерактивного взаимодействия запросы и ответы разделены пустыми строками, чтобы наглядно показать процесс взаимодействия. В настоящем взаимодействии с программой жюри пустых строк не будет, их также не следует выводить, однако после каждого запроса, а также после вывода ответа необходимо выводить перевод строки.