Назад
 Начало |
 Соревнования |
| 2007 |
Подразделы
Другие разделы
Дата и время
16/11/2024 17:14:49
Задачи очного тура региональной олимпиады по информатике
1. Игра "Наказание жадности" 2. Ковбой и поросенок 3. Разные цифры 4. Прыжки по буквам 5. Треугольники
4. Прыжки по буквам
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 15/04/2007 | Региональная олимпиада Информатика-2007 (4) |
| 19/11/2010 | Занятие 10 (B) |
| 09/12/2010 | Сборы 31 (4D) |
| 11/02/2013 | Занятие 16 (A) |
| 07/04/2022 | «Базовая олимпиадная подготовка» (second level) - Одномерная динамика (проводит novink) (E) |
| 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
