Вам задана бинарная строка \(s\) (строка, состоящая только из символов 0 и/или 1).
Вы можете выполнять операции двух типов над \(s\):
- удалить один символ из \(s\). Эта операция стоит \(1\) монету;
- поменять местами любую пару символов в \(s\). Эта операция бесплатна (стоит \(0\) монет).
Вы можете выполнять эти операции в любом порядке любое количество раз.
Давайте обозначим строку, которую вы получили после выполнения вышеуказанных операций, как \(t\). Строка \(t\) является хорошей, если для каждого \(i\) от \(1\) до \(|t|\) \(t_i \neq s_i\) (\(|t|\) — длина строки \(t\)). Пустая строка — всегда хорошая. Обратите внимание, что вы сравниваете результирующую строку \(t\) с исходной строкой \(s\).
Какова минимальная суммарная стоимость сделать строку \(t\) хорошей?
Выходные данные
Для каждого набора входных данных выведите минимальную суммарную стоимость сделать строку \(t\) хорошей.
Примечание
В первом наборе вам нужно удалить символ из \(s\), чтобы получить пустую строку \(t\). Только после этого \(t\) станет хорошей. Одно удаление стоит \(1\).
Во втором тесте вы, например, можете удалить второй символ из \(s\), чтобы получить строку 01, а затем поменять местами первый и второй символы, чтобы получить строку \(t\) \(=\) 10. Строка \(t\) — хорошая, так как \(t_1 \neq s_1\) и \(t_2 \neq s_2\). Общая стоимость составляет \(1\).
В третьем тесте вы, например, можете поменять местами \(s_1\) с \(s_2\), \(s_3\) с \(s_4\), \(s_5\) с \(s_7\), \(s_6\) с \(s_8\) и \(s_9\) с \(s_{10}\). Вы получите строку \(t\) \(=\) 1010001110. Все операции обмена бесплатны, поэтому общая стоимость составляет \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0
011
0101110001
111100
|
1
1
0
4
|