Олимпиадный тренинг

Задача . Clumsy Cows


Задача

Темы: Линейные алгоритмы

Определите минимальное количество символов в строке из круглых скобок, которые нужно заменить на противоположный ( левую скобку на правую, или наоборот) , чтобы получить сбалансированную строку.
Существует несколько способов определить сбалансированную строку скобок. Например, такой: В строке должно быть одинаковое количество левых и правых скобок, и для любого ее префикса количество левых скобок должно быть не меньше, чем количество правых скобок.
Например, эти строки - сбалансированные () (()) ()(()())
А эти - нет: )( ())( ((())))
PROBLEM NAME: clumsy
Формат входных данных
* Строка 1: строка из скобок длиной не более 100,000 символов.


Формат выходных данных
* Строка 1: Одно целое число - минимальное количество скобок, которые нужно "переключить" , чтобы конвертировать заданную строку в сбалансированную.


Примечание
Последняя скобка должна быть переключена и одна из двух средних.
Примеры
№Входные данныеВыходные данные
1 
())(
 
2
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


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

Загруженные файлы
Нет