Дана бинарная строка $$$s$$$ длины $$$2n$$$, каждый элемент которой равняется $$$\mathtt{0}$$$ или $$$\mathtt{1}$$$. Вы можете выполнять следующую операцию:
Ваша задача — найти последовательность из не более чем $$$10$$$ операций, изменяющую все элементы $$$s$$$ на $$$\mathtt{0}$$$, или определить, что это невозможно. Заметим, что минимизировать количество операций не обязательно.
При заданных ограничениях можно доказать, что если существует способ изменить все элементы $$$s$$$ на $$$\mathtt{0}$$$, то существует способ, требующий не более $$$10$$$ операций.
$$$^\dagger$$$ Скобочная последовательность называется правильной, если ее можно превратить в корректное математическое выражение, добавив символы $$$+$$$ и $$$1$$$. Например, последовательности «(()()», «()» и «(()(())» являются правильными, а «)(», «(()» и «(())(» — не являются.
$$$^\ddagger$$$ Если мы выполним операцию инвертирования для подотрезка с $$$l$$$ по $$$r$$$ бинарной строки $$$s$$$, то мы инвертируем все значения $$$s_i$$$ такие, что $$$l \leq i \leq r$$$. Если $$$s_i$$$ инвертируется, то мы присваиваем $$$s_i := \mathtt{0}$$$, если изначально было $$$s_i = \mathtt{1}$$$, и наоборот. Например, если $$$s=\mathtt{1000101}$$$ и мы выполняем операцию инвертирования подотрезка с $$$3$$$ по $$$5$$$, то $$$s$$$ изменится на $$$s=\mathtt{1011001}$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — где $$$2n$$$ — длина строки $$$s$$$.
Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$2n$$$ ($$$s_i = \mathtt{0}$$$ или $$$s_i = \mathtt{1}$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите в единственной строке $$$-1$$$, если невозможно изменить все элементы $$$s$$$ на $$$\mathtt{0}$$$.
В противном случае выведите одно целое число $$$k$$$ ($$$0 \le k \le 10$$$), равняющееся количеству операций, необходимому для изменения всех элементов $$$s$$$ на $$$\mathtt{0}$$$. Затем в следующих $$$k$$$ строках выведите правильные скобочные последовательности длины $$$2n$$$, представляющие собой операции, необходимые для изменения всех элементов $$$s$$$ на $$$0$$$.
Если существует несколько способов изменить все элементы $$$s$$$ на $$$\mathtt{0}$$$, требующих не более $$$10$$$ операций, то можно вывести любой из них.
4101200003100111401011100
-1 2 ()() ()() 1 (())() 2 (((()))) ()()(())
В первом наборе входных данных можно показать, что невозможно изменить все элементы $$$s$$$ на $$$\mathtt{0}$$$.
Во втором наборе входных данных первая операция с использованием последовательности скобок $$$b = \mathtt{()()}$$$ преобразует двоичную строку $$$s=\mathtt{0000}$$$ в $$$s=\mathtt{1111}$$$. Затем вторая операция с использованием той же последовательности скобок $$$b = \mathtt{()()}$$$ преобразует двоичную строку $$$s=\mathtt{1111}$$$ обратно в $$$s=\mathtt{0000}$$$. Заметим, что поскольку все элементы $$$s$$$ изначально уже равнялись $$$\mathtt{0}$$$, то использование $$$0$$$ операций также является правильным ответом.
В третьем наборе входных данных одна операция с использованием последовательности скобок $$$b = \mathtt{(())()}$$$ изменит все элементы $$$s$$$ на $$$\mathtt{0}$$$. Операция будет происходить следующим образом:
В четвертом наборе входных данных первая операция с использованием скобочной последовательности $$$b = \mathtt{(((())))}$$$ преобразует бинарную строку $$$s = \mathtt{01011100}$$$ в $$$s = \mathtt{11111001}$$$. Затем, вторая операция с использованием скобочной последовательности $$$b = \mathtt{()()(())}$$$ преобразует бинарную строку $$$s = \mathtt{11111001}$$$ в $$$s=\mathtt{00000000}$$$.
Название |
---|