← 返回题目列表

AtCoder · agc054_d

D. (牛)

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

分数: 1000 点

问题陈述

给定的是一个字符串 S 组成 (, ), o,和 x。 您可以交换两个相邻的字符 S 任意次数。 求满足以下条件所需的最小交换次数。

  • 让我们制作一个字符串 S' 组成 ( 和 ) 通过替换每个出现的 o 与 () 以及每次出现 x 与 )( in S。 然后, S' 是 平衡括号字符串.
平衡括号字符串的定义

平衡括号字符串是以下字符串之一:

  • 空字符串;
  • 一个串联的字符串 s, t 按此顺序,其中 s 和 t 是一些非空平衡括号字符串;
  • 一个串联的字符串 (, s, ) 按此顺序,其中 s 是一些平衡的括号字符串。

在这个问题的约束下,总是可以达到目的的。

约束

  • S 是一个由以下组成的字符串 (, ), o,和 x.
  • S 包含相同的非零数量 (和 )s。
  • |S| \leq 8000

输入

输入由标准输入按以下格式给出:

S

输出

打印答案。


示例输入 1

)x(

示例输出 1

3

我们应该这样做: )x( → x)( → x() → (x)。 在这里,我们有 S'=()(),这是一个平衡的括号字符串。


示例输入 2

()ox

示例输出 2

2

示例输入 3

()oxo(xxx))))oox((oooxxoxo)oxo)ooo(xxx(oox(x)(x()x

示例输出 3

68