Repariere die Klammersequenz
Angenommen, wir haben einen String
s, der aus öffnenden und schließenden Klammern besteht. Es ist erlaubt, einige öffnende Klammern in schließende zu ändern und umgekehrt. Wie viele Änderungen sind mindestens nötig, um eine gültige Klammersequenz zu erhalten?Eingabe
Die einzige Zeile der Eingabe enthält den String
s (1 ≤ |s| ≤ ). Es ist garantiert, dass die Länge von s gerade ist.Ausgabe
Das Programm soll die kleinste Anzahl an Änderungen ausgeben, die erforderlich ist, um die Klammersequenz gültig zu machen.
Beispiele
Eingabe | Ausgabe |
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Erklärung
- ()(( → ()() ⇒ 1 Änderung
- )( → () ⇒ 2 Änderungen
- ()() ⇒ keine Änderungen erforderlich
- ((() → ()() ⇒ 2 Änderungen
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB