Сначала напомним, что расстояние Левенштейна между двумя строками
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 = 6. Длина текста
s в каждом наборе входных данных не превышает 1000. Оценка за этот тест: 30 баллов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1
5
when the imposter is sus
2
2
when composter
2
has bus
|
3 2
|