← 返回题目列表

AtCoder · tenka1_2016_qualB_b

B. 天下一魔法发电

中文机器翻译题面 查看原题

配点 : 400 点

問題文

天下一魔法发电厂是一座可以利用神秘魔法发电的发电厂。

用于产生魔力的燃料是以下字符串。 S 。

S 是 您也可以写 ( 和 按字典顺序比较 ) 它包括S 包含偶数个字符。

通过使用天下一文字处理器将这个字符串重写为相应的字符串,你将能够成功地产生魔力。

以下字符串是兼容的。

  • () 是匹配的字符串。 当
  • T 是匹配字符串时,(T) 也是一个匹配的字符串。
  • T, U 是匹配字符串时,TU也是一个匹配的字符串。

Tenkaichi字处理器有以下四种操作。

首先,光标位于 指 S 的第一个字符。

  1. 向右移动光标(如果光标指向最后一个字符,则不会移动)
  2. 向左移动光标(如果光标指向第一个字符,则不会移动)
  3. 光标指向的字符是 ( ,字符 更改为 ) 更改为
  4. 光标指向的字符是 ) ,字符 更改为 ( 更改为

例如 如果 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