Codeforces Beta Round 98 (Div. 2) |
---|
Закончено |
Прочитав половину книги «Буря и затишье» на уроках информатики, Иннокентий был полон решимости дочитать книгу на математике. И все было хорошо, пока учительница математики Елена Олеговна не увидела, что Иннокентий вместо решения уравнений пятой степени занят литературой. Поскольку Иннокентий на прошлом уроке предложил алгоритм решения уравнений пятой степени в общем случае, у Елены Олеговны не оставалось другого выбора, как дать ему новое задание.
Учительница попросила записать подряд без пробелов все слова из книги «Буря и затишье» в одну длинную строку s. По ее мнению строка является хорошей, если количество гласных букв в строке не более чем вдвое больше количества согласных. Другими словами, строка, в которой v гласных и c согласных, является хорошей тогда и только тогда, когда v ≤ 2c.
Задача, которую должен решить Иннокентий, оказалась достаточно простой: необходимо найти количество наибольших по длине хороших подстрок строки s.
В единственной строке входных данных задана непустая строка s, состоящая из не более чем 2·105 строчных и заглавных латинских букв. Гласными будем считать буквы «a», «e», «i», «o», «u», а также их заглавные варианты.
Выведите в одну строку через пробел два числа: максимальную длину хорошей подстроки, а также количество максимальных по длине хороших подстрок. Если не существует ни одной хорошей подстроки, выведите «No solution» без кавычек.
Две подстроки считаются различными, если их позиции вхождения различны. Значит, если какая-то строка встречается несколько раз, то она должна быть учтена такое же количество раз.
Abo
3 1
OEIS
3 1
auBAAbeelii
9 3
AaaBRAaaCAaaDAaaBRAaa
18 4
EA
No solution
В первом примере есть только одна наидлиннейшая хорошая подстрока: сама «Abo». Остальные хорошие подстроки имеют меньшую длину: «b», «Ab», «bo».
Во втором примере есть только одна наидлиннейшая хорошая подстрока: «EIS». Остальные хорошие подстроки: «S», «IS».
Название |
---|