Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
181. Прыжки по буквам
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 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) |
Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дана цепочка из `N` символов, состоящая из прописных латинских букв. Необходимо пройти с первого символа цепочки до последнего символа, прыгая не более чем на `K` символов. Стоимость прыжка, при котором символ не меняется, равна 0, а стоимость прыжка на другой символ равна 1.
Напишите программу, вычисляющую наименьшую стоимость перехода с первого на последний символ.
В первой строке ввода содержатся два целых числа – длина цепочки `N\ (1≤N≤1000000)` и максимальная длина прыжка `K\ (1≤K≤N)`. В второй строке содержится цепочка из `N` прописных латинских букв.
Вывести одно целое число – минимальную стоимость перехода.
Пример ввода
10 2 ABABBCACBC
Вывод для примера
2
