Задача 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 |