Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дана строка, состоящая из 0 и 1.
Необходимо переставить некоторые символы в строке так, чтобы в получившейся строке подстрока 00 появлялась ровно один раз.
Напишите программу, которая определяет минимальное количество обменов символов в заданной строке
для получения строки с единственной подстрокой 00.
Первая строка ввода содержит строку из 0 и 1.
Вывести одно целое число - минимальное количество обменов.
Если невозможно переставить символы в строке так, чтобы получить строку с единственной подстрокой 00, то вывести -1.
```sample Пример ввода 1
1001
```
```sample Пример вывода 1
0
```
```sample Пример ввода 2
0100000111
```
```sample Пример вывода 2
2
```
```sample Пример ввода 3
10000
```
```sample Пример вывода 3
-1
```
Пояснение к примеру 1: В исходной строке ничего не нужно менять.
Пояснение к примеру 2: Нужно выполнить 2 обмена, например, 5-й символ строки с 10-м и 7-й с 8-м.
Получится строка 0100101010.
Пояснение к примеру 3: Возможные перестановки строки: 10000 (3 подстроки 00), 01000 (2 подстроки 00), 00100 (2 подстроки 00), 00010 (2), 00001 (3).
После любых перестановок в строке будет не менее 2 подстрок 00.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (50 баллов)||
Длина строки от 2 до 15 символов.
В этой подзадаче 10 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 2 (50 баллов)||
Необходимые подзадачи: 1.
Длина строки от 16 до 1000 символов.
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте.
Начало
Рабочее место участника
Динамическое программирование и запоминающие функции