Задача Bracket2019. Дана послідовність круглих дужок. За одну секунду ви можете поміняти місцями будь-які дві дужки. За який мінімальний час ви зможете отримати правильну послідовність дужок? Дужковий вираз вважається правильним, якщо:
- він є порожнім
- якщо A та B правильні, то AB правильний
- якщо A правильний, то (A) правильний
Технічні умови. Програма Bracket2019 читає з пристрою стандартного введення послідовність дужок довжиною не більше 106 символів і виводить на пристрій стандартного виведення шуканий час. Якщо отримати правильну послідовність дужок неможливо, програма повинна вивести -1.
Приклади.
|
Виведення |
|
|
((())) )()( (( |
0 1 -1 |