Вам дано целое число $$$n$$$ и строка $$$s$$$, состоящая из $$$2^n$$$ строчных букв латинского алфавита. Обозначим символы строки $$$s$$$ как $$$s_0s_1s_2\cdots s_{2^n-1}$$$.
Строка $$$t$$$ длины $$$2^n$$$ (символы которой будем обозначать как $$$t_0t_1t_2\cdots t_{2^n-1}$$$) называется XOR-ированием строки $$$s$$$, если существует целое число $$$j$$$ ($$$0\le j \leq 2^n-1$$$) такое, что для всех $$$0 \leq i \leq 2^n-1$$$ выполняется $$$t_i = s_{i \oplus j}$$$ (здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ).
Найдите лексикографически минимальное XOR-ирование строки $$$s$$$.
Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 18$$$).
Вторая строка содержит строку $$$s$$$, состоящую из $$$2^n$$$ строчных букв латинского алфавита.
Выведите одну строку, содержащую лексикографически минимальное XOR-ирование строки $$$s$$$.
2 acba
abca
3 bcbaaabb
aabbbcba
4 bdbcbccdbdbaaccd
abdbdccacbdbdccb
5 ccfcffccccccffcfcfccfffffcccccff
cccccffffcccccffccfcffcccccfffff
1 zz
zz
В первом примере лексикографически минимальное XOR-ирование $$$t$$$ строки $$$s =$$$«acba» является «abca». Это XOR-ирование, так как для $$$j = 3$$$ получаем:
Во втором примере лексикографически минимальное XOR-ирование соответствует выбору числа $$$j = 4$$$ из определения XOR-ирования.
В третьем примере лексикографически минимальное XOR-ирование соответствует выбору числа $$$j = 11$$$ из определения XOR-ирования.
В четвертом примере лексикографически минимальное XOR-ирование соответствует выбору числа $$$j = 10$$$ из определения XOR-ирования.
В пятом примере лексикографически минимальное XOR-ирование соответствует выбору числа $$$j = 0$$$ или числа $$$j = 1$$$ из определения XOR-ирования.
Название |
---|