printЗадачи очного тура региональной олимпиады по информатике

print4. Прыжки по буквам

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дана цепочка из `N` символов, состоящая из прописных латинских букв. Необходимо пройти с первого символа цепочки до последнего символа, прыгая не более чем на `K` символов. Стоимость прыжка, при котором символ не меняется, равна 0, а стоимость прыжка на другой символ равна 1.
Напишите программу, вычисляющую наименьшую стоимость перехода с первого на последний символ.
В первой строке ввода содержатся два целых числа – длина цепочки `N\ (1≤N≤1000000)` и максимальная длина прыжка `K\ (1≤K≤N)`. В второй строке содержится цепочка из `N` прописных латинских букв.
Вывести одно целое число – минимальную стоимость перехода.

Пример ввода

10 2
ABABBCACBC

Вывод для примера

2
loading