Сначала напомним, что расстояние Левенштейна между двумя строками
s
и
t
это минимальное число операций: "добавить символ", "удалить символ" и "изменить один символ на другой", которое нужно применить к строке
s
, чтобы получить строку
t
. Например, расстояние между строками
s = aba
и
t = dac
равняется 3: можно применить такую последовательность операций:
aba → ab → ac → dac
.
Длинный текст
s
был зачитан, записан и разрезан на несколько кусков. Затем каждый из кусков был распознан и преобразован обратно в текст - получился набор строк
A
. К сожалению, преобразования были неидеальными. В результате в текст могли добавиться или пропасть слова, также некоторые слова могли измениться на похожие.
Строка s и каждая строка из
A
имеет такие свойства: каждый символ в этих строках либо маленькая латинская буква, либо пробел. Никакая строка не может начинаться или заканчиваться на пробел, в строках не может быть двух пробелов подряд.
Ваша задача: разбить текст
s
на
|A|
частей (назовем это разбиение
S
) так, чтобы отличие между
A
и
S
было минимальным. Отличием двух наборов одинаковой длины
A
и
S
назовем значение
\(\sum_{i=1}^{|A|}dist(A_i, S_i)\), где
dist(Ai,Si) -
расстояние Левенштейна между строками
Ai
и
Si
.
Важно, что разрезать текст вы можете только по пробелам, причем этот пробел не будет входить ни в один из отрезков (то есть он пропадает). То есть разбиение
S
можно описать количеством слов (подстрок между двумя пробелами или концами исходной строки) в каждой строке разбиения.
Для лучшего понимания, рассмотрим пример: Пусть текст
s
равен "
when the imposter is sus
". Также пусть преобразование через аудио дало нам набор
A
из двух строк: первая равняется "
when composter
", а вторая равняется "
has bus
". Тогда, если мы разделим текст
s
так, чтобы в первой строке было 3 слова, а во второй 2, то набор
S
будет равняться [
when the imposter, is sus
]. Тогда отличием наборов
A
и
S
будет значение
dist(when the imposter, when composter) + dist(is sus, has bus)
. Посчитав расстояния Левенштейна, получим, что отличие равно 5 + 3 = 8.
В первой строке входных данных записано число
t
количество наборов входных данных. Затем идут описания наборов.
В первой строке набора дается одно число
n
количество слов в тексте
s
.
Во второй строке набора дается текст
s
, содержащий
n
слов.
В третьей строке содержится одно число
|A|
количество строк в разбиении.
Далее каждая строка из разбиения
A
описывается двумя строками ввода: в первой содержится количество слов в этой строке, а во второй сама строка.
Для каждого набора входных данных выведите
|A|
положительных чисел количество слов в данной строке вашего разбиения
S
. Также сумма этих чисел должна равняться количеству слов в строке
s
.
Оценка за каждый набор входных данных будет вычисляться по формуле
5·(jury_diff/participant_diff)
, где
participant_diff
отличие
A
и разбиения участника, а
jury_diff
минимальное отличие, которое смогло получить жюри или участники. Оценкой за тест будет сумма оценок за все наборы входных
данных.
Во этой задаче
t = 14
. Длина текста
s
в каждом наборе входных данных не превышает 10
4. Во время тура проверяется, что сумма выведенных чисел совпаедет с количеством слов в строке.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1
5
when the imposter is sus
2
2
when composter
2
has bus
|
3 2
|