Задача . C. Социальная дистанция

Поликарп с друзьями хочет сходить в новый ресторан. Ресторан представляет из себя \(n\) столиков, расставленных вдоль прямой. За некоторыми столиками уже сидят люди. Столики пронумерованы от \(1\) до \(n\) в порядке слева направо. Состояние ресторана описывается строкой длины \(n\), которая содержит символы '1' (столик занят) и '0' (столик свободен).

Правила ресторана запрещают людям садиться на расстоянии \(k\) или меньше друг от друга. То есть, если человек сидит за столиком номер \(i\), то все столики с номерами от \(i-k\) до \(i+k\) (кроме \(i\)-го) должны быть свободны. Иными словами, разница (то есть модуль разности) номеров между любыми двумя занятыми столиками должна быть строго больше \(k\).

Например, если \(n=8\) и \(k=2\), то:

• строки «10010001», «10000010», «00000000», «00100000» соответствуют правилам ресторана;
• строки «10100100», «10011001», «11111111» не соответствуют правилам ресторана, так как в каждой из них есть пара единиц на расстоянии меньшем или равном \(k=2\).

В частности, если состояние ресторана описывается строкой без единиц или строкой с одной единицей, то требование ресторана выполнено.

Вам задана бинарная строка \(s\), которая описывает текущее состояние ресторана. Гарантируется, что для строки \(s\) правила ресторана выполнены.

Найдите максимальное количество свободных столиков, которые можно занять, чтобы не нарушить правила ресторана. Формально, какое максимальное количество нулей можно заменить на единицы так, что требование все еще будет выполняться?

Например, если \(n=6\), \(k=1\), \(s=\) «100010», то ответ на задачу будет \(1\), так как есть только один свободный столик на позиции \(3\), который можно занять в соответствии с правилами ресторана.