← 返回题目列表

Codeforces · 1970/A2

A2. 平衡随机播放(中)

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

此问题与简单版本的差异以粗体突出显示。

括号序列是由字符“(”和“)”组成的字符串,例如“(()((”)。

平衡括号序列是插入数字和运算后可以成为有效数学表达式的括号序列,例如“(()(()))”。

括号序列的平衡定义为左括号“(”的数量减去右括号“)”的数量。例如,序列“(()((”)的余额为3。

平衡括号序列也可以定义为平衡为 0 的括号序列,使得其每个前缀都具有非负平衡。

我们定义平衡洗牌操作,它采用括号序列并返回括号序列,如下所示:首先,对于输入序列的每个字符,我们计算该字符之前的序列前缀的平衡性,并将其与输入序列中字符的位置一起写在表中,例如:

前缀余额01212321位置12345678字符(()(()))

然后,我们按前缀平衡的升序对该表的列进行排序,并按位置的降序排列打破联系。在上面的例子中,我们得到:

前缀余额01112223位置18427536字符()(()())

该表的最后一行形成另一个括号序列,在本例中为“()(()())”。该序列称为对输入序列应用平衡洗牌操作的结果,或者简称为输入序列的平衡洗牌。

令人惊讶的是,任何平衡括号序列的平衡洗牌总是另一个平衡括号序列(为了简洁,我们将省略证明)。更令人惊讶的是,两个不同的平衡括号序列的平衡洗牌总是不同的,因此平衡洗牌操作是任意给定长度的平衡括号序列集合上的双射(我们也将省略这个证明)。

给您一个平衡的括号序列。求其原像:平衡括号序列,其平衡洗牌等于给定序列。

输入

输入的唯一一行包含仅由字符“(”和“)”组成的字符串$$$s$$$。该字符串保证是一个非空的平衡括号序列,其长度不超过$$$1\,000$$$。

输出

打印平衡括号序列 $$$t$$$,使得 $$$t$$$ 的平衡洗牌等于 $$$s$$$。保证答案始终存在且唯一。

示例

输入 #1

()(()())

输出 #1

(()(()))