Задача №114054. Строка и перестановка
Вам дана строка \(s_1 s_2 \ldots s_n\), состоящая из \(n\) маленьких английских букв. Жюри загадало перестановку \(p_1, p_2, \ldots, p_n\) и получило новую строку \(t\), поставив \(i\)-й символ строки \(s\) на \(p_i\)-ю позицию в строке \(t\). Вам необходимо найти строку \(t\).
Для этого вы можете один раз задать вопрос, состоящий из \(k\) выбранных вами пар индексов. Для пары индексов \((a_i, b_i)\) (\(1 \leq i \leq k\), \(1 \leq a_i < b_i \leq n\)) вы узнаете, верно ли, что \(p_{a_i} < p_{b_i}\).
Вы хотите определить искомую строку, спросив про наименьшее количество пар, то есть минимизируя значение числа \(k\), при условии, что проверяющая программа является адаптивной. Это означает, что ответ к каждому тесту может быть различен в зависимости от того, про какие пары индексов вы спрашиваете. Другими словами, ваше решение должно успешно восстанавливать строку \(t\) для любой возможной перестановки \(p_1, p_2, \ldots, p_n\).
Сначала вам необходимо считать непустую строку \(s\), состоящую из маленьких английских букв. Длина строки не превосходит \(100\).
Затем вы должны вывести строку, содержащую единственное целое число \(k\) (\(0 \leq k \leq 10 ^ 4\)), а после — \(k\) строк, в \(i\)-й из которых будет содержаться два целых числа \(a_i\) и \(b_i\) (\(1 \leq a_i < b_i \leq n\)) — пара, про которую вы хотите спросить.
После этого, если \(k > 0\) (то есть вы спросили про какие-то пары), вы должны считать строку, состоящую из \(k\) символов, \(i\)-й символ которой равен « 1 », если \(p_{a_i} < p_{b_i}\), и « 0 » в противном случае. Если ваша программа задала некорректный запрос, то вместо строки с ответами на запросы может быть задана строка « -1 », если проверяющая программа жюри смогла считать и распознать ваш запрос, а затем определить его как некорректный. В случае, если ваш запрос не был распознан проверяющей системой или произошёл другой сбой, например, вы не вывели ничего или вывели слишком много чисел, вердикт проверяющий системы может быть разным.
После получения ответов на все запросы, вам необходимо вывести ответ — строку \(t\). После вывода ответа ваша программа должна завершиться.
Обратите внимание, после вывода ответа или в случае считывания строки « -1 » вы обязательно должны сразу завершить вашу программу. В противном случае вердикт тестирующей системы может быть некорректным, в частности, вы можете получить вердикт Run-time error или Time limit exceeded!
Не забывайте сбрасывать буфер после каждого запроса. Например, на языке C++ надо использовать функцию fflush(stdout) или вызов cout.flush() , на Java вызов System.out.flush() , на Pascal flush(output) и stdout.flush() для языка Python.
В первом примере сделан запрос про пару индексов \((1, 2)\), в ответ получена строка « 1 », что означает, что \(p_1 < p_2\), и, следовательно, загадана перестановка \(p = \)«\(1\) \(2\)», то есть искомая строка — « ab ».
Во втором примере сделан запрос про пару индексов \((1, 2)\), в ответ получена строка « 0 », это означает, что \(p_1 \geq p_2\), и, следовательно, загадана перестановка \(p = \)«\(2\) \(1\)», то есть искомая строка — « ba ».
В третьем примере не спрашивается ни про какие пары индексов, а сразу выводится ответ — строка « qqq ».
В четвертом примере была загадана перестановка «\(2\) \(3\) \(1\)».
Тесты к этой задаче состоят из четырёх подзадач. Баллы за каждую подзадачу ставятся только при прохождении всех тестов подзадачи и всех тестов необходимых подзадач.
ab 1 2
Correct answer! Queries: 1
ab 2 1
Correct answer! Queries: 1
qqq 2 3 1
Correct answer! Queries: 0
baa 2 3 1
Correct answer! Queries: 2