Это упрощенная версия задачи. Единственная разница между двумя версиями состоит в том, что более сложная версия дополнительно требует минимального количества подотрезков.
У Tokitsukaze есть бинарная строка \(s\) длины \(n\), состоящая только из нулей и единиц, \(n\) является четным.
Tokitsukaze делит \(s\) на минимальное количество непрерывных подотрезков, так чтобы в каждом подотрезке все биты были одинаковы. После этого \(s\) считается хорошей, если длины всех подотрезков четны.
Например, если \(s\) равна «11001111», она будет разделена на «11», «00» и «1111». Их длины равны \(2\), \(2\), \(4\) соответственно, все числа четные, поэтому «11001111» хорошая. Другой пример, если \(s\) равна «1110011000», она будет разделена на «111», «00», «11» и «000», а их длины равны \(3\), \(2\), \(2\), \(3\). Очевидно, что «1110011000» не является хорошей.
Tokitsukaze хочет улучшить \(s\), изменив значения некоторых позиций в \(s\). В частности, она может выполнить следующую операцию любое количество раз: изменить значение \(s_i\) на «0» или «1»(\(1 \leq i \leq n\)). Можете ли вы назвать ей минимальное количество операций, чтобы сделать \(s\) хорошей?
Примечание
В первом наборе входных данных один из способов сделать \(s\) хорошей следующий.
Измените \(s_3\), \(s_6\) и \(s_7\) на «0», после чего \(s\) станет «1100000000», ее можно разделить на «11» и «00000000», длина которых составляют \(2\) и \(8\) соответственно. Есть и другие способы за \(3\) операции сделать \(s\) хорошей, например, можно получить в итоге «1111110000», «1100001100», «1111001100».
Во втором, третьем и четвертом наборах входных данных \(s\) изначально хорошая, поэтому никаких действий не требуется.