e-olymp
Соревнования

February 21 - March 3. Dynamic Programming

Исправить расстановку скобок

В заданной строке из скобок требуется изменить наименьшее количество символов так, чтобы полученная строка была правильной. Удалять или вставлять символы нельзя.

Всего имеется три вида скобок: обычные (), квадратные [] и фигурные {}. Каждая пара скобок содержит соответственно открывающийся ('(', '[', '{' ) и закрывающийся (')', ']', '}') символ.

Правильная строка определяется следующими правилами:

  • Пустая строка является правильной.
  • Если строка s правильная, то правильными являются также (s), [s] и {s}.
  • Если строки s и t правильные, то правильной будет строка st.

Например, строки "([{}])", "" и "(){}[]" являются правильными, а "([}]", "([)]" и "{" нет.

Для заданной строки следует изменить наименьшее количество символов так, чтобы она стала правильной.

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

Каждая строка содержит четное количество символов '(', ')', '[', ']', '{', '}'. Длина каждой строки не более 50.

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

Для каждой скобочной записи вывести в отдельной строке наименьшее количество символов, которое можно изменить так, чтобы строка стала правильной.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
([{}])()[]{}
([)]
([{}[]
Выходные данные
0
2
1