Два числа $$$a$$$ и $$$b$$$ записаны в двоичной системе счисления. Запись обоих имеет длину $$$2n$$$. Обе записи разбиты на $$$n$$$ блоков по 2 стоящие рядом цифры. В каждом из чисел вы можете сколько угодно раз менять два произвольных блока местами. Какое максимальное значение может быть у результата применения побитовой операции XOR к получившимся числам?
Определим операцию побитового исключающего «ИЛИ» (XOR). Пусть даны два целых неотрицательных двоичных числа $$$x$$$ и $$$y$$$ длины $$$k$$$ (возможно с ведущими нулями): $$$x_{k-1} \dots x_2 x_1 x_0$$$ и $$$y_{k-1} \dots y_2 y_1 y_0$$$. Здесь $$$x_i$$$ это $$$i$$$-й бит числа $$$x$$$, а $$$y_i$$$ это $$$i$$$-й бит числа $$$y$$$. Пусть $$$r = x ~ \text{XOR} ~ y$$$ — результат операции XOR над числами $$$x$$$ и $$$y$$$. Тогда двоичной записью $$$r$$$ будет $$$r_{k-1} \dots r_2 r_1 r_0$$$, где: $$$$$$ r_i = \begin{cases} 1, ~ \text{если} ~ x_i ~ \neq ~ y_i \\ 0, ~ \text{если} ~ x_i ~ = ~ y_i \end{cases} $$$$$$
В первой строке содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — количество блоков по две цифры в записях обоих числах. Во второй строке задана запись числа $$$a$$$. В третьей строке задана запись числа $$$b$$$.
Для удобства блоки разделены символом «|».
В единственной строке вам необходимо вывести одно двоичное число из $$$n$$$ блоков, которое является ответом на задачу, в таком же блочном формате, в каком заданы числа $$$a$$$ и $$$b$$$.
2 00|11 00|10
11|10
3 00|00|00 00|00|00
00|00|00
3 10|10|01 00|01|01
11|11|01
В первом примере можно поменять два соседних блока в первом числе, получится $$$11|00\ \ \text{XOR}\ \ 00|10 = 11|10$$$.
Во втором примере любая перестановка цифр не меняет $$$a \ \ \text{XOR} \ \ b$$$. Обратите внимание, что длина выводимого числа должна состоять из $$$n$$$ блоков, поэтому надо выводить блоки из лидирующих нулей.
В третьем примере можно получить $$$101001$$$ из $$$a$$$ и $$$010100$$$ из $$$b$$$.
В данной задаче $$$50$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$2$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$1 \leq n \leq 8$$$, наберут не менее $$$20$$$ баллов.
Решения, корректно работающие при $$$a$$$, состоящем только из цифры $$$0$$$, наберут не менее $$$10$$$ баллов.
Решения, корректно работающие, когда $$$a$$$ и $$$b$$$ состоят только из блоков $$$00$$$ и $$$01$$$, наберут не менее $$$10$$$ баллов.
Решения, корректно работающие, когда $$$a$$$ состоит только из блоков $$$00$$$ и $$$01$$$, а $$$b$$$ состоит только из блоков $$$00$$$ и $$$10$$$, наберут не менее $$$20$$$ баллов.