Փակագծերի հաջորդականությունը շտկել
Տրված է բացող և փակող փակագծերից կազմված s տողը։ Թույլատրելի է որոշ բացող փակագծերը փոխարինել փակողներով և որոշ փակող փակագծերը փոխարինել բացողներով։ Հարցը հետևյալն է․ առնվազն քանի գործողություն է անհրաժեշտ, որպեսզի հաջորդականությունը դառնա վավեր։
Մուտք
Մուտքի միակ տողում տրված է s (1 ≤ |s| ≤ ) տողը։ Երաշխավորվում է, որ s-ի երկարությունը զույգ է։
Ելք
Ծրագիրը պետք է տպի ամենափոքր փոփոխությունների քանակը, որն անհրաժեշտ է, որպեսզի հաջորդականությունը վավեր դառնա։
Օրինակներ
Մուտք | Ելք |
|---|---|
()(( | 1 |
)( | 2 |
()() | 0 |
((() | 1 |
Բացատրություն
()(( → ()() ⇒ 1 փոփոխություն
)( → () ⇒ 2 փոփոխություն
()() ⇒ փոփոխություններ չեն պահանջվում
((() → ()() ⇒ 2 փոփոխություն
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB