Задача №1979. Контрольная работа
Студенты пришли на занятия в большую аудиторию и все сели на какие-то места первого ряда аудитории. Пришедший преподаватель объявил, что сейчас состоится контрольная работа, и решил пересадить студентов так, чтобы никакие два студента не сидели на двух подряд идущих местах (чтобы между любыми двумя студентами всегда было как минимум одно свободное место).
Помогите преподавателю пересадить минимальное число студентов, чтобы достичь нужного результата.
Сначала вводится натуральное число N — количество мест в первом ряду аудитории, а затем число K — количество студентов. Далее в порядке возрастания перечислены номера мест, на которые студенты сели изначально (все места пронумерованы числами от 1 до N).
1 ≤ K ≤ 1000, 2K–1 ≤ N ≤ 109.
Выведите одно число — минимальное количество студентов, которых придется пересадить.
Решение для n <= 15 будет набирать 30 баллов, для n <= 3000 будет набирать 60 баллов.
7 4 2 4 6 7
3
8 4 2 4 6 7
1