Codeforces Round 809 (Div. 2) |
---|
Закончено |
У вас есть последовательность $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$, состоящая из целых чисел от $$$1$$$ до $$$m$$$. Также у вас есть строка $$$s$$$, состоящая из $$$m$$$ латинских букв «B».
Вы примените $$$n$$$ операций к этой строке.
Найдите лексикографически минимальную строку, которую Вы можете получить после выполнения всех операций.
Строка $$$x$$$ лексикографически меньше строки $$$y$$$ такой же длины, если и только если в первой позиции, где $$$x$$$ и $$$y$$$ различны, в строке $$$x$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$y$$$.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных. Далее следуют описания этих наборов.
В первой строке дано два числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 50$$$) — длина последовательности $$$a$$$ и длина строки $$$s$$$.
Во второй строке даны $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — последовательность $$$a$$$.
Для каждого набора входных данных выведите строку длины $$$m$$$ — лексикографически минимальную строку, которую можно получить. Каждый символ строки должен быть заглавной латинской буквой «A» или заглавной латинской буквой «B».
64 51 1 3 11 524 11 1 1 12 41 32 77 54 55 5 3 5
ABABA BABBB A AABB ABABBBB ABABA
В первом наборе входных данных последовательность $$$a = [1, 1, 3, 1]$$$. Одно из возможных решений следующее.
Во втором наборе входных данных вы сделаете только одну операцию. Вы можете заменить $$$2$$$-й либо $$$4$$$-й символ строки $$$s$$$ на A. Вы можете получить строки BABBB и BBBAB после операции. Строка BABBB является лексикографически наименьшей из этих строк.
В третьем наборе входных данных вы можете получить только строку A.
В четвёртом наборе входных данных вы можете заменить $$$1$$$-й и $$$2$$$-й символы строки $$$s$$$ на A, чтобы получить строку AABB.
В пятом наборе входных данных вы можете заменить $$$1$$$-й и $$$3$$$-й символы строки $$$s$$$ на A, чтобы получить строку ABABBBB.
Название |
---|