Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Защищенный пароль

 Очень надежная и совершенно бесплатная операционная система «Vokna» известна своей безопасностью, так как при проектировании разработчики уделили большое внимание проблемам генерации паролей. Ядро операционной системы содержит в себе строку S длиной N символов. Генерация пароля происходит с использованием символов строки S. Паролем будем называть подстроку Si,j строки S длиной не менее одного и не более N символов. Подстрокой Si,j строки S называется строка, последовательно составленная из символов S[i], S[i+1], S[i+2], … , S[j-1], S[j]. Символы в строке нумеруются последовательно начиная с единицы. Пароль Si,j считается защищенным, если в нем встречается не более K одинаковых символов. Вашей задачей является по заданной строке S и числу K определить количество различных вариантов выбора защищенного пароля. Два варианта выбора пароля  S1i,j  и  S2l,m называются различными, если iили jm.

 

Входные данные:

 Первая строка входного файла содержит два натуральных числа N (1 N106) и (1 KN), разделенных одиночным пробелом,  где N – количество символов в строке S; K – максимальное количество одинаковых символов в пароле.

Вторая строка входного файла содержит ровно N символов. Каждый символ является либо маленькой латинской буквой, либо цифрой.

Каждая строка входного файла заканчивается символом перевода строки.

Выходные данные:

 Единственная строка выходного файла должна содержать одно целое число – количество вариантов выбора защищенного пароля.

 


Примеры:
input.txt output.txt
1 6 2
7aaarr
15
2 4 1
ayay
7

Сложность задачи: 50%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 41, зарегистрированных 4:
Marichka, cor Sabrr, Fate, Myronets21,
[Данные за последние 5 минут]