Задача №1814. Дана строка
Рассмотрим множество строк, состоящих из строчных букв латинского алфавита. Пусть вес буквы «a» равен 1, вес буквы «b» равен 2, вес буквы «c» равен 3, ..., вес буквы «z» равен 26. Строка \(S\) называется окружностью радиуса \(R\), если существует такая позиция p, что сумма весов букв слева от \(p\) равна \(R\) и сумма весов букв справа от \(p\) равна \(R\). Например, строка «abcab» является окружностью радиуса 3, строка «abcabd» является окружностью радиуса 6, но строка «abba» не является окружностью.
Дана строка \(T\), состоящая из \(N\) строчных букв латинского алфавита. Отрезок [\(l\), \(r\)] является \(K\)-хорошим, если подстрока \(T\), начинающаяся в позиции \(l\) и заканчивающаяся в позиции \(r\), является окружностью радиуса \(K\). Отрезок [\(l\), \(r\)] является \(K\)-красивым, если подстрока \(T\), начинающаяся в позиции \(l\) и заканчивающаяся в позиции \(r\), является окружностью радиуса не более \(K\)
Множество отрезков, объединением которых является отрезок [1, \(N\)], называется \(K\)-хорошим (\(K\)-красивым) покрытием строки \(T\), если оно состоит только из \(K\)-хороших (\(K\)-красивых) отрезков. Требуется найти мощность минимального \(K\)-хорошего (\(K\)-красивого) покрытия строки \(T\).
Первая строка входного файла содержит строку \(T\) длины \(N\), состоящую из не более чем \(10^6\) строчных букв латинского алфавита. Вторая строка входного файла содержит два целых числа \(K\) и \(Q\), 0 \(\le\) \(K\) \(\le\) \(10^9\), 1 \(\le\) \(Q\) \(\le\) 2.
Если \(Q\) равно 1, то выведите мощность минимального \(K\)-хорошего покрытия строки \(T\), если \(Q\) равно 2, то выведите мощность минимального \(K\)-красивого покрытия строки \(T\). В случае, если искомого \(K\)-хорошего (\(K\)-красивого) покрытия не существует, выведите −1.
Гарантируется, что если \(Q\)=2 и \(10^4\) < \(N\), то строка \(T\) состоит только из букв «a» и «b».
abcabdz 10 2
2
abcabd 6 1
1
abcabdz 4 2
3