Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Скобочки - 2

(Время: 1 сек. Память: 16 Мб Сложность: 57%)

Напомним, что называется правильной скобочной последовательностью:

  • пустая строка является правильной скобочной последовательностью;
  • если строка а — правильная скобочная последовательность, то строки (а), [а] — тоже правильные скобочные последовательности;
  • если строки а и b — правильные скобочные последовательности, то строка ab — тоже правильная скобочная последовательность.

Задана строка S, состоящая из квадратных и круглых скобок. Разрешается заменять квадратную открывающую скобку ([) на круглую открывающую (() и наоборот, а также квадратную закрывающую скобку (]) на круглую закрывающую ()) и наоборот.

За одно действие разрешается изменить ровно один символ строки. Необходимо за минимальное число действий преобразовать S в правильную скобочную последовательность.

Входные данные

Входной файл INPUT.TXT содержит строку S. Ее длина не превосходит 100 000 символов.

Выходные данные

В выходной файл OUTPUT.TXT выведите искомое минимальное число действий или -1, если преобразовать S в правильную скобочную последовательность невозможно.

Примеры

INPUT.TXTOUTPUT.TXT
1(())[]0
2[(])2
3((]]]-1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483