Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Internetsharing

Задача Internetsharing

Учасники літньої школи потерпають від нестачі інтернету - адже він потрібен усім! Тож Григорій Ісаакович вирішив поділитися ним з усіма. Ноутбуки учасників ЛШ мають особливість - вони можуть ділитися доступом до інтернету з іншими ноутбуками, якщо самі мають доступ до нього і якщо відстань між ними не більше за D кімнат. Іншими словами, якщо у i-ій кімнаті є  ноутбук з доступом до інтернету, у j-ій кімнаті він обов'язково також буде, якщо |i - j| <= D. Усього у корпусі N кімнат (1 <= N <= 300000, 1 <= D <= N). Якісь кімнати мають ноутбук, якісь ні. Вам необхідно знайти мінімальну кількість ноутбуків, яких не вистачає для того, щоб у останній кімнаті був доступ до інтернету (ноутбук Григорія Ісааковича роздає інтернет з кімнати №1).

Технічні умови:

Програма internetsharing має зчитувати з екрану (пристрою стандартного введення) цілі числа N і D, після чого зчитати N чисел (нулів чи одиничок). Якщо i-те число - одиниця, то у i-ій кімнаті вже є ноутбук, інакше немає. В першій і останній кімнатах ноутбуки вже гарантовано є.

Програма має виводити єдине число - відповідь на задачу.

Введення

Виведення

4 1

1 0 1 1

1

 

5 2

1 0 0 0 1

1

8 2

1 1 0 0 1 0 0 1

2


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"