Codeforces Round 897 (Div. 2) |
---|
Закончено |
Вам дана бинарная строка $$$s$$$ длины $$$n$$$ (строка - состоящая только из $$$0$$$ и $$$1$$$). Число $$$x$$$ является хорошим, если существует такая бинарная строка $$$l$$$ длины $$$n$$$, содержащая $$$x$$$ единиц, что если каждый символ $$$s_i$$$ заменить на $$$s_i \oplus l_i$$$ (где $$$\oplus$$$ обозначает операцию Побитового исключающего ИЛИ) то строка $$$s$$$ станет палиндромом.
Нужно вывести бинарную строку $$$t$$$ длины $$$n+1$$$, где $$$t_i$$$ ($$$0 \leq i \leq n$$$) равно $$$1$$$ если число $$$i$$$ хорошее, и $$$0$$$ иначе.
Палиндром — это строка, которая читается одинаково как слева направо, так и справа налево. Например, строки 01010, 1111, 0110 — палиндромы.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$).
Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите одну строку $$$t$$$ длины $$$n+1$$$ - ответ на задачу.
561010115000009100100011310011
0010100 111111 0011111100 0110 11
Рассмотрим первый пример.
Название |
---|