Փակագծերի հաջորդականությունը շտկել
Տրված է բացող և փակող փակագծերից կազմված
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