G. Обработка строки
| Имя входного файла: | processing.in |
| Имя выходного файла: | processing.out |
| Ограничение по времени: | 2 s |
| Ограничение по памяти: | 256 megabytes |
В новых процессорах, проектируемых корпорацией MBI, для работы со строками выделен отдельный сопроцессор. Этому сопроцессору можно передать строку, состоящую из строчных символов латинского алфавита, и программу, описывающую обработку строки. После этого процессор задумается и, через долю секунды, вернет результат обработки строки.
Работа еще не завершена, поэтому пока что он умеет обрабатывать строки только одним способом. Строка, которую ему передают на ввод, должна состоять из 2k символов, а программа обработки этой строки – из 2k - 1 чисел, каждое из которых является нулем или единицей.
Если строка, поданная на вход сопроцессору, состоит из одного символа, то результат обработки равен этой же строке. Если строка длиннее, то выполняются следующие действия.
Сначала он разобьет строку на две части равной длины, а программу – на три части. При этом длины первых двух частей программы будут равны между собой, а третьей частью будет последнее число программы. После этого первая половина строки превратится в результат ее обработки первой частью программы, а вторая – в результат ее обработки второй частью программы. После этого, если оставшееся число равно нулю, вторая половина строки будет дописана справа к первой, если же оно равно единице – первая половина будет дописана справа ко второй.
Так, например, если на вход сопроцессору подана строка <<abcd>> и программа (0, 1, 1), то результатом обработки будет строка <<dcab>>.
Вам поступило предложение принять участие в его тестировании. Отказаться от такого лестного предложения вы не смогли, поэтому теперь вам необходимо научиться составлять программу для сопроцессора, с помощью которой он преобразует строку S в строку T, или же определять, что такой программы не существует.
Формат входного файла
Первая строка входного файла содержит одно целое число n – количество случаев, которые вам необходимо разобрать. В следующих строках описаны сами n случаев.
Первая строка описания очередного случая содержит строку S, состоящую только из строчных букв латинского алфавита. Длина строки S равна 2k, где 1 ≤ k ≤ 16. Вторая строка описания очередного случая содержит строку T, также состоящую только из строчных букв латинского алфавита. Длина строки T равна длине строки S.
Суммарная длина всех строк S в одном входном файле не превышает 100,000.
Формат выходного файла
Для каждого случая в очередной строке выходного файла слово <<Yes>>, если программа для сопроцессора, преобразовывающая строку S в строку T существует, и <<No>> в противном случае.
Если ответ <<Yes>>, в следующей строке выведите 2k - 1 чисел, разделенных пробелами – программу, которую для этого преобразования необходимо передать сопроцессору. Если таких программ несколько – выведите любую.
Пример:
| processing.in | processing.out |
|---|---|
| 2 abacabab baababca abacabab bbaaabca | Yes 0 1 0 1 0 0 1 No |
Источник: Командный чемпионат школьников Карелии по программированию, 4 ноября 2012
Обсудить
Отправить решение