Codeforces Round 638 (Div. 2) |
---|
Закончено |
У Феникса есть строка $$$s$$$, состоящая из строчных букв латинского алфавита. Он хочет распределить все буквы своей строки по $$$k$$$ непустым строкам $$$a_1, a_2, \dots, a_k$$$ так, что каждая буква из $$$s$$$ попадет ровно в одну из строк $$$a_i$$$. Строки $$$a_i$$$ не обязаны быть подстроками $$$s$$$. Феникс может распределить буквы $$$s$$$ и переупорядочить их внутри каждой строки $$$a_i$$$ так как захочет.
Например, если $$$s = $$$ baba и $$$k=2$$$, Феникс может распределить буквы своей строки множеством способов, в том числе:
Однако получить такие варианты он не может:
Феникс хочет разделить свою строку $$$s$$$ на $$$k$$$ строк $$$a_1, a_2, \dots, a_k$$$ так, чтобы минимизировать лексикографически максимальную строку среди них, т. е. минимизировать $$$max(a_1, a_2, \dots, a_k)$$$. Помогите ему найти оптимальное распределение и выведите минимально возможное значение $$$max(a_1, a_2, \dots, a_k)$$$.
Строка $$$x$$$ лексикографически меньше, чем строка $$$y$$$, если либо $$$x$$$ является префиксом $$$y$$$ (и $$$x \ne y$$$), либо существует такой индекс $$$i$$$ ($$$1 \le i \le min(|x|, |y|))$$$, что $$$x_i$$$ < $$$y_i$$$ и для всех $$$j$$$ $$$(1 \le j < i)$$$ $$$x_j = y_j$$$. Здесь $$$|x|$$$ обозначает длину строки $$$x$$$.
Входные данные состоят из нескольких наборов. В первой строке задано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Каждый набор состоит из двух строк.
В первой строке каждого набора задано два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 10^5$$$) — длина строки $$$s$$$ и количество не пустых строк, в которые Феникс хочет распределить буквы $$$s$$$, соответственно.
Во второй строке каждого набора задана строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных $$$\le 10^5$$$.
Выведите $$$t$$$ ответов — по одному на набор входных данных; $$$i$$$-й ответ — минимально возможный $$$max(a_1, a_2, \dots, a_k)$$$ в $$$i$$$-м наборе.
6 4 2 baba 5 2 baacb 5 3 baacb 5 3 aaaaa 6 4 aaxxzz 7 1 phoenix
ab abbc b aa x ehinopx
В первом наборе входных данных, одно из оптимальных решений — разбить baba на ab и ab.
Во втором наборе входных данных, одно из оптимальных решений — разбить baacb на abbc и a.
В третьем наборе, одно из оптимальных решений — разбить baacb на ac, ab и b.
В четвертом наборе, одно из оптимальных решений — разбить aaaaa на aa, aa и a.
В пятом наборе, одно из оптимальных решений — разбить aaxxzz на az, az, x и x.
В шестом наборе, одно из оптимальных решений — разбить phoenix на ehinopx.
Название |
---|