Скобочки - 2
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
Напомним, что называется правильной скобочной последовательностью:
- пустая строка является правильной скобочной последовательностью;
- если строка а — правильная скобочная последовательность, то строки (а), [а] — тоже правильные скобочные последовательности;
- если строки а и b — правильные скобочные последовательности, то строка ab — тоже правильная скобочная последовательность.
Задана строка S, состоящая из квадратных и круглых скобок. Разрешается заменять квадратную открывающую скобку ([) на круглую открывающую (() и наоборот, а также квадратную закрывающую скобку (]) на круглую закрывающую ()) и наоборот.
За одно действие разрешается изменить ровно один символ строки. Необходимо за минимальное число действий преобразовать S в правильную скобочную последовательность.
Входные данные
Входной файл INPUT.TXT содержит строку S. Ее длина не превосходит 100 000 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите искомое минимальное число действий или -1, если преобразовать S в правильную скобочную последовательность невозможно.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | (())[] | 0 |
| 2 | [(]) | 2 |
| 3 | ((]]] | -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
