06/04/2025 17:26:15

Рабочее место участника

Задачи

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

Ограничения: время – 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

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

15/04/2007	Региональная олимпиада Информатика-2007 (4)
19/11/2010	Занятие 10 (B)
09/12/2010	Сборы 31 (4D)
11/02/2013	Занятие 16 (A)
23/02/2023	Базовый уровень: динамическое программирование 1 (проводит BOGAT) (H)
10/07/2023	Лето 2023-7 простые (E)
27/02/2024	Динамическое программирование 1 (проводит BOGAT) (H)
08/07/2024	Лето 2024-7 простые (E)
19/03/2025	ЦОП1: динамическое программирование (проводит BOGAT) (I)