ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > ВКОШП-2016 > задача:


Задача 06

Гость
• Вопросы к жюри (4)

Задачи сборника

• Задача 01
• Задача 02
• Задача 03
• Задача 04
• Задача 05
• Задача 06
• Задача 07
• Задача 08
• Задача 09

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 40000/40000/40000/40000 мс. Лимит памяти 10340/65000/65000/65000 Кб.

Ровно год назад правителю планеты Мурмариан на день рожденья подарили побеги диковинного растения "Kaktus Koluchkus", которое должно очень красиво цвести. К растению правитель получил и подробную инструкцию, которую не стал читать, и поручил высадить полученные побеги прямо перед его дворцом в цветочные горшки. Прошли годы, но растения так и не зацвели. Раздосадованный правитель отругал садовника и попросил его решить эту проблему.
После прочтения инструкции стало понятно, что растения высадили с нарушениями правил. Как оказалось, побеги нельзя высаживать в двух подряд идущих цветочных горшках.

Помогите садовнику пересадить манимальное количество растений "Kaktus Koluchkus" так, чтобы они не росли в двух подряд стоящих горшках (чтобы между любыми двумя горшками всегда был как минимум один свободный горшок)

Ввод:

Сначала вводятся два натуральных числа: N — количество цветочных горшков перед дворцом и K — количество растений "Kaktus Koluchkus". Далее в порядке возрастания перечислены К номеров горшков, в которые были посажены растения "Kaktus Koluchkus" (все горшки пронумерованы числами от 1 до N)..
1 <= K <= 1000, 2K–1 <= N <= 109.

Вывод:

Выведите одно число — минимальное количество растений "Kaktus Koluchkus", которые придется пересадить.

Пример:

Ввод Вывод
7 4
2 4 6 7
3
8 4
2 4 6 7
1
Для отправки решений необходимо выполнить вход.

www.contester.ru