Corrigir a sequência de parênteses
Dada uma string
s composta por parênteses de abertura e de fechamento, é permitido mudar alguns parênteses de abertura para fechamento e vice-versa. Qual é o número mínimo de operações necessárias para obter uma sequência de parênteses válida?Entrada
A única linha da entrada contém a string
s (1 ≤ |s| ≤ ). Garante-se que o comprimento de s é par.Saída
O programa deve imprimir o menor número de modificações necessárias para que a sequência se torne válida.
Exemplos
Entrada | Saída |
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Explicação
- ()(( → ()() ⇒ 1 modificação
- )( → () ⇒ 2 modificações
- ()() ⇒ nenhuma modificação necessária
- ((() → ()() ⇒ 2 modificações
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB