配点 : 400 点
問題文
天下一魔法发电厂是一座可以利用神秘魔法发电的发电厂。
用于产生魔力的燃料是以下字符串。 S 。
S 是
您也可以写 ( 和
按字典顺序比较 ) 它包括S 包含偶数个字符。
通过使用天下一文字处理器将这个字符串重写为相应的字符串,你将能够成功地产生魔力。
以下字符串是兼容的。
()是匹配的字符串。 当T是匹配字符串时,(T)也是一个匹配的字符串。T,U是匹配字符串时,TU也是一个匹配的字符串。
Tenkaichi字处理器有以下四种操作。
首先,光标位于 指 S 的第一个字符。
- 向右移动光标(如果光标指向最后一个字符,则不会移动)
- 向左移动光标(如果光标指向第一个字符,则不会移动)
- 光标指向的字符是
(,字符 更改为)更改为 - 光标指向的字符是
),字符 更改为(更改为
例如 如果 S 是以下字符串:
())(()))
通过操作 1、4、 您可以创建具有以下对应关系的字符串:
(()(()))
。
电厂负责人富德先生想将字符串改写成运算次数最少的对应字符串。 给定了
S ,因此求最少的操作次数将其重写为匹配的字符串。
制約
- S 中的字符数 |S| 是偶数
- 2 \leq |S| \leq 100
入力
输入是按以下格式从标准输入给出的。
S
出力
输出重写对应字符串所需的最少操作次数。在输出末尾插入换行符。
入力例 1
())(()))
出力例 1
2
这是问题文本中出现的情况。
入力例 2
((((
出力例 2
5
通过操作1,1,3,1,3,您将得到匹配的字符串。 (这称为
入力例 3
)))(((
出力例 3
9