Вам задана гирлянда, состоящая из $$$n$$$ ламп. Состояния ламп описываются строкой $$$s$$$ длины $$$n$$$. $$$i$$$-й символ строки $$$s_i$$$ равен '0', если $$$i$$$-я лампа выключена, или '1', если $$$i$$$-я лампа включена. Вам также задано положительное целое число $$$k$$$.
За один ход вы можете выбрать одну лампу и изменить ее состояние (то есть включить ее, если она выключена, и наоборот).
Гирлянда называется $$$k$$$-периодичной, если расстояние между каждой парой соседних включенных ламп равно в точности $$$k$$$. Рассмотрим случай $$$k=3$$$. Тогда гирлянды «00010010», «1001001», «00010» и «0» являются хорошими, а гирлянды «00101001», «1000001» и «01001100» не являются хорошими. Заметьте, что гирлянда не является цикличной, то есть первая включенная лампа не идет после последней включенной лампы и наоборот.
Ваша задача — найти минимальное количество ходов, необходимое для того, чтобы получить $$$k$$$-периодичную гирлянду из заданной.
Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 25~ 000$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.
Первая строка набора тестовых данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^6; 1 \le k \le n$$$) — длину $$$s$$$ и необходимый период. Вторая строка набора тестовых данных содержит строку $$$s$$$, состоящую из $$$n$$$ символов '0' и '1'.
Гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превосходит $$$10^6$$$ ($$$\sum n \le 10^6$$$).
Для каждого набора тестовых данных выведите ответ — минимальное количество ходов, необходимое для того, чтобы получить $$$k$$$-периодичную гирлянду из заданной.
6 9 2 010001010 9 3 111100000 7 4 1111111 10 3 1001110101 1 1 1 1 1 0
1 2 5 4 0 0
| Codeforces Round 642 (Div. 3) |
|---|
| Закончено |
