题目详情题解（0）讨论（0）提交记录（0）

AT_abc064_d.[ABC064D] Insertion

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个由 NN 个字符组成的字符串 SS，该字符串仅包含 ( 和 )。你可以在 SS 中插入若干个 ( 或 )，以构造一个合法的括号序列。
合法的括号序列定义如下：

  • () 是合法的括号序列。
  • 如果 XX 是合法的括号序列，则将 (、XX、) 按顺序连接得到的字符串也是合法的括号序列。
  • 如果 XX 和 YY 都是合法的括号序列，则将 XX 和 YY 按顺序连接得到的字符串也是合法的括号序列。
  • 其他括号序列均为不合法。

请你求出通过在 SS 中插入 ( 或 ) 所能得到的最短长度的合法括号序列。如果有多个满足条件的答案，输出字典序最小的那个。

输入格式

输入以以下格式从标准输入中给出。

NN SS

输出格式

请输出通过在 SS 中插入 ( 或 ) 所能得到的最短长度的合法括号序列中，字典序最小的那个字符串。

输入输出样例

  • 输入#1

    3
())

    输出#1

    (())

  • 输入#2

    6
)))())

    输出#2

    (((()))())

  • 输入#3

    8
))))((((

    输出#3

    (((())))(((())))

说明/提示

限制条件

  • SS 的长度为 NN。
  • 1≤N≤1001 \leq N \leq 100
  • SS 仅由 ( 和 ) 组成。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页