Bessie the cow is trying to type a balanced string of parentheses into her new laptop, but she is sufficiently clumsy (due to her large hooves) that she keeps mis-typing characters. Please help her by computing the minimum number of characters in the string that one must reverse (e.g., changing a left parenthesis to a right parenthesis, or vice versa) so that the string would become balanced.

A string of parentheses is "balanced" if there are the same total number of ('s and )'s, and for any prefix of the string there are at least as many ('s as )'s.

Line 1: A string of parentheses of even length at most 100,000 characters.

A single integer giving the minimum number of parentheses that must be toggled to convert the string into a balanced string.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > November > Silver