text из строчных латинских букв и целое число divisor. Гласными считаются буквы a, e, i, o, u, все остальные — согласные.
Непустой отрезок строки (подряд идущие символы) назовём **сбалансированным**, если:
- гласных и согласных в нём поровну;
- произведение числа гласных на число согласных делится на divisor.
Посчитайте, сколько сбалансированных отрезков в text. Отрезки, стоящие на разных позициях, считаются разными, даже если совпадают как строки.
Перебор всех отрезков работает за O(n²); строка бывает длиной до 5·10⁴ — нужно что-то быстрее.text="tobeor", divisor=4 → 2
Подходят "tobe" (2 гласные, 2 согласные, 2·2 = 4 делится на 4) и "beor" (тоже 2 и 2). У всей строки 3 и 3, а 9 на 4 не делится. У отрезков из двух букв вроде "to" и "be" произведение 1·1 = 1 на 4 не делится.
text="kayak", divisor=1 → 6
При divisor = 1 годится любой отрезок с равным числом гласных и согласных: "ka", "ay", "ya", "ak", "kaya", "ayak" — всего 6.
text="rhythm", divisor=3 → 0
Гласных нет вовсе, поэтому подходящих отрезков нет.
text состоит только из строчных латинских буквtext="tobeor", divisor=4
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 92 теста на сервере, включая скрытые.