Вам дана бинарная строка\(^\dagger\) \(s\) длины \(n\).
Бинарная строка \(p\) той же длины \(n\) называется хорошей, если для каждого \(i\) (\(1 \leq i \leq n\)) существуют индексы \(l\) и \(r\) такие, что:
- \(1 \leq l \leq i \leq r \leq n\)
- \(s_i\) является модой\(^\ddagger\) строки \(p_lp_{l+1}\ldots p_r\)
Вам дана другая бинарная строка \(t\) длины \(n\). Найдите минимальное расстояние Хэмминга\(^\S\) между \(t\) и любой хорошей строкой \(g\).
\(^\dagger\) Бинарная строка — это строка, состоящая только из символов \(\mathtt{0}\) и \(\mathtt{1}\).
\(^\ddagger\) Символ \(c\) является модой строки \(p\) длины \(m\), если число вхождений \(c\) в \(p\) не меньше \(\lceil \frac{m}{2} \rceil\). Например, \(\mathtt{0}\) является модой \(\mathtt{010}\), \(\mathtt{1}\) не является модой \(\mathtt{010}\), и оба \(\mathtt{0}\) и \(\mathtt{1}\) являются модами \(\mathtt{011010}\).
\(^\S\) Расстояние Хэмминга между строками \(a\) и \(b\) длины \(m\) — это количество индексов \(i\) таких, что \(1 \leq i \leq m\) и \(a_i \neq b_i\).
Выходные данные
Для каждого набора входных данных выведите минимальное расстояние Хэмминга между \(t\) и любой хорошей строкой \(g\).
Примечание
В первом наборе входных данных \(g=\mathtt{000}\) — это хорошая строка, которая имеет расстояние Хэмминга \(0\) от \(t\).
Во втором наборе входных данных \(g=\mathtt{0011}\) — хорошая строка, имеющая расстояние Хэмминга \(2\) от \(t\). Можно доказать, что не существует хороших строк с расстоянием Хэмминга меньше \(2\) от \(t\).
В третьем наборе входных данных \(g=\mathtt{001100}\) — хорошая строка, имеющая расстояние Хэмминга \(1\) от \(t\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
000
000
4
0000
1111
6
111111
000100
|
0
2
1
|