Kotlin Heroes 5: ICPC Round |
---|
Закончено |
Поликарп только что закончил записывать очередную лекцию по эльфийским языкам. На этой неделе был язык «VwV» (произносится «уву»). В письменности данного языка используются только две латинские строчные буквы 'v' и 'w'.
К сожалению, Поликарп записал лекцию курсивом и абсолютно без пробелов, поэтому вся запись выглядит как нескончаемая последовательность закорючек. Если быть точным, то Поликарп не может отличить 'w' от 'vv' в своей записи, так как и то, и другое состоит из двух одинаковых закорючек.
К счастью, его брат Монокарп пишет гораздо лучше, поэтому Поликарп смог позаимствовать его запись, и теперь хочет улучшить свою с ее помощью. Чтобы это сделать, он может следовать за записью Монокарпа и подчеркивать некоторые буквы в своей записи так, чтобы не осталось неоднозначностей. Если он подчеркивает букву 'v', то ее становится нельзя перепутать с частью буквы 'w', а если он подчеркивает 'w', то ее становится нельзя перепутать с двумя рядом стоящими буквами 'v'.
Какое минимальное количество букв необходимо подчеркнуть Поликарпу, чтобы запись стала однозначной?
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.
В каждой из следующих $$$t$$$ строк записана непустая строка на языке VwV, которая состоит только из строчных латинских букв 'v' и 'w'. Длина строки не превосходит $$$100$$$.
Для каждого набора входных данных выведите одно целое число: минимальное количество букв, которые необходимо подчеркнуть Поликарпу, чтобы запись стала однозначной.
5 vv v w vwv vwvvwv
1 0 1 1 3
В первом наборе входных данных достаточно подчеркнуть одну из двух букв 'v'.
Во втором наборе входных данных буква 'v' сама по себе однозначна, поэтому не надо подчеркивать нечего.
В третьем наборе входных данных необходимо подчеркнуть 'w', чтобы не перепутать ее с двумя буквами 'v'.
В четвертом наборе входных данных можно подчеркнуть 'w', чтобы избавиться от всех неоднозначностей.
В пятом наборе входных данных можно подчеркнуть обе буквы 'w', а также одну из двух букв 'v' между ними.
Название |
---|