Arreglar la secuencia de paréntesis
Dado un string s compuesto de paréntesis de apertura y cierre, se permite cambiar algunos paréntesis de apertura a paréntesis de cierre y algunos paréntesis de cierre a paréntesis de apertura. ¿Cuál es el mínimo número de operaciones necesarias para lograr una secuencia de paréntesis válida?
Entrada
La única línea de la entrada contiene el string s (1 ≤ |s| ≤ ). Se garantiza que la longitud de s sea par.
Salida
El programa debe imprimir la menor cantidad de modificaciones necesarias para que la secuencia sea válida.
Ejemplos
Entrada | Salida |
|---|---|
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Explicación
()(( → ()() ⇒ 1 modificación
)( → () ⇒ 2 modificaciones
()() ⇒ no se necesitan modificaciones
((() → ()() ⇒ 2 modificaciones
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB