Problem:


Score : 400 points

Problem Statement

You are given a string S of length N consisting of ( and ). Your task is to insert some number of ( and ) into S to obtain a correct bracket sequence.

Here, a correct bracket sequence is defined as follows:  

() is a correct bracket sequence.

If X is a correct bracket sequence, the concatenation of (, X and ) in this order is also a correct bracket sequence.

If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.

Every correct bracket sequence can be derived from the rules above.

Find the shortest correct bracket sequence that can be obtained. If there is more than one such sequence, find the lexicographically smallest one.

Constraints

The length of S is N.

1 ≤ N ≤ 100

S consists of ( and ).

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the lexicographically smallest string among the shortest correct bracket sequences that can be obtained by inserting some number of ( and ) into S.

Sample Input 1

3
())

Sample Output 1

(())

Sample Input 2

6
)))())

Sample Output 2

(((()))())

Sample Input 3

8
))))((((

Sample Output 3

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



Sample input:
3
())


Sample output:
(())

Submission status: Accepted

Solution code:
from sys import stdin, exit
N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
count, l, r = 0, 0, 0

for i in range(len(S)):
    if S[i] == '(':
        count += 1
    else:
        if count == 0:
            l += 1
        else:
            count -= 1
r = count
ans = ""
for i in range(l):
    ans += '('
ans += S
for i in range(r):
    ans += ')'
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
cnt_l = 0
cnt_r = 0
for s in S:
    if s == '(':
        cnt_l += 1
    else:
        if cnt_l > 0:
            cnt_l -= 1
        else:
            cnt_r += 1
print('('*cnt_r+S+')'*cnt_l)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
l=[]
ctl=0;ctr=0
for i in range(n):
  if s[i]=='(':
    ctl+=1
  else:
    ctr+=1
  if ctl<ctr:
    l.append('(')
    ctl+=1
l.reverse()
for i in range(ctl-ctr):
  s.append(')')
s=l+s
print(''.join(s))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

def main():
    _ = int(input())
    S = input().strip()
    ans = ""
    l = r = 0
    for c in S:
        if c == "(":
            r += 1
        elif c == ")":
            if r > 0:
                r -= 1
            else:
                l += 1
    ans = "("*l + S + ")"*r
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()

l_cnt = 0
res = ''

for s in S:
    if s == '(':
        l_cnt += 1
        res += s
    else:
        if l_cnt == 0:
            res = '(' + res
        else:
            l_cnt -= 1
        res += s

res += ')' * l_cnt

print(res)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
count = 0
flag = 0
while flag == 0:
    flag = 1
    dep = 0
    for i in S:
        if i == ")":
            dep += 1
        else:
            dep -= 1
        if dep > 0:
            break
    if dep > 0:
        S = "("*dep + S
        flag = 0
    elif dep < 0:
        S = S + ")"*(-dep)
        flag = 0
    #print(S)
print(S)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def S(): return input()

def main():
    N = I()
    s = S()
    Left = ""

    countO = 0
    for x in s:
        if x==")" and countO == 0:
            Left = "("+Left
        elif x==")":
            countO -= 1
        elif x=="(":
            countO += 1
    return(Left+s+")"*countO)


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
n = int(input())
s = input()

left = 0
leftplus = 0
for i in range(len(s)):
    if s[i] == '(':
        left += 1
    else:
        if left == 0:
            leftplus += 1
        else:
            left -= 1

right = 0
rightplus = 0
r = s[::-1]
for i in range(len(r)):
    if r[i] == ')':
        right += 1
    else:
        if right == 0:
            rightplus += 1
        else:
            right -= 1
print('('*leftplus + s + ')'*rightplus)

Submission status: Accepted

Solution code:
N=int(input())
S=input()

b,k=0,0
for i in range(N):
  if S[i]=="(":
    b+=1
  else:
    k+=1
    if b>0:
      k-=1
      b-=1
  #print(b,k)

print("("*k+S+")"*b)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
S = list(input().strip())

lc = 0
rc = 0

for i in range(N):
    t = S[i]

    if t == ")":
        if lc > 0:
            lc -= 1
        else:
            rc += 1
    else:
        lc += 1

print("(" * rc + "".join(S) + ")" * lc)

Submission status: Accepted

Solution code:
import copy
n=int(input())
s=input()
ans=copy.deepcopy(s)
paren=0
for i in range(n):
    if(s[i] == '('):
        paren+=1
    elif(paren <= 0):
        ans = "(" + ans
    else:
        paren-=1

for i in range(paren):
    ans = ans + ")"

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
s = S[:]
while "()" in s:
  s = s.replace("()", "")
r = s.count("(")
l = s.count(")")
print("(" * l + S + ")" * r)

Submission status: Accepted

Solution code:
input()
s=input()
x=y=0
for c in s:
	if c=="(":
		x+=1
	else:
		x-=1
	y=max(y,-x)
print("("*y+s+")"*(x+y))

Submission status: Accepted

Solution code:
input();S=input();d=m=0
for c in S:
 if c=="(":d-=1
 else:d+=1
 m=max(d,m)
S="("*m+S;d=m=0
for c in S[::-1]:
 if c=="(":d+=1
 else:d-=1
 m=max(d,m)
print(S+")"*m)

Submission status: Accepted

Solution code:
def solve(S):
    # N < 100

    pendings = 0
    prefix = 0
    for c in S:
        if c == '(':
            pendings += 1
        elif c == ')':
            pendings -= 1
        if pendings < 0:
            pendings = 0
            prefix += 1
    answer = '('*prefix + S
    if pendings > 0:
        answer += ')'*(pendings)
    print(answer)

N = int(input())
S = input()
solve(S)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

# r: (
# l: )

# '(' をいくつ足せばよいか？
ans_r, r = 0, 0
for i in range(N):
    if S[i] == ')':
        if r >= 1:
            r -= 1
        else:
            ans_r += 1
    else:
        r += 1

# ')' をいくつ足せばよいか？
ans_l, l = 0, 0
for i in range(N):
    if S[N-1-i] == '(':
        if l >= 1:
            l -= 1
        else:
            ans_l += 1
    else:
        l += 1

print('('*ans_r + S + ')'*ans_l)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
S3=[]
for i in range(len(S)):
  S3.append(S[i])
  if S3.count("(") < S3.count(")") :
    S3 =["("] + S3
  if i == len(S) - 1:
    for j in range(S3.count("(") - S3.count(")")):
      S3.append(")")
      
print("".join(S3))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
T = []
c = 0
m = 0
for s in S:
  if s == ")":
    c += 1
  else:
    if c > 0:
      m += c #先頭につける"("の数
      c = 0
    c -= 1
  if c > 0:
    m += c #先頭につける"("の数
    c = 0
print("("*m + S + ")"*(-c))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    s = input().strip()
    stock_l = 0
    left = ""
    right = ""
    for i in range(N):
        if s[i] == "(":
            stock_l += 1
        else:
            if stock_l > 0:
                stock_l -= 1
            else:
                left += "("
    print(left + s + ")" * stock_l)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
r=0;l=0
for i in s:
    if i=="(":
        r+=1
    else:
        if r==0:
            l+=1
            continue
        r-=1
print("("*l+s+")"*r)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    S = input()
    count = 0
    t = ""
    for c in S:
        if c == "(":
            count += 1
        else:
            count -= 1

        if count == -1:
            t = "(" + t + c
            count += 1
        else:
            t += c
    t += ")" * count
    return t


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:

n = int(input())
s = input()

l = 0
r = 0
for i in range(n):
    if s[i] == "(":
        l += 1
    else:
        l = max(0, l-1)
for i in range(n-1, -1, -1):
    if s[i] == ")":
        r += 1
    else:
        r = max(0, r-1)

print("(" * r + s + ")" * l)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a=b=0
k=0
for i in range(n):
	if s[i]=="(":
		a+=1
	else:
		b+=1
	if a<b:
		k+=1
		a+=1
s=k*("(")+s
if a>b:
	s+=")"*(a-b)
print(s)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
left=[]
right=[]
for c in S:
    if c == ')':
        if not right:
            left.append('(')
        else:
            right.pop()
    elif c == '(':
        right.append(')')
print(''.join(left) + S + ''.join(right))

Submission status: Accepted

Solution code:
N, S = int(input()), input()
stk = []
for s in S:
    if len(stk) == 0 or stk[-1] == ')' or s == '(':
        stk.append(s)
    else:
        stk.pop()

print('(' * stk.count(')') + S + ')' * stk.count('('))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    cnt = 0
    pre = 0
    for i in range(len(S)):
        if S[i] == '(':
            cnt += 1
        else:
            cnt -= 1
            if cnt < 0:
                pre = max(pre, -cnt)
    
    ans = "(" * pre + S
    cnt = 0
    for j in range(len(ans)):
        if ans[j] == '(':
            cnt += 1
        else:
            cnt -= 1

    print(ans + ')' * cnt)

main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
stack = []
for s in S:
    if s == '(':
        stack.append('(')
    elif s == ')':
        if len(stack) == 0 or stack[-1] == ')':
            stack.append(')')
        elif stack[-1] == '(':
            stack.pop()

l, r = sum([1 for s in stack if s == '(']), sum([1 for s in stack if s == ')'])
print('(' * r + S + ')' * l)

Submission status: Accepted

Solution code:
N, S = open(0)
S = S.strip()

cnt = left = 0
for s in S:
    if s == "(":
        cnt += 1
    else:
        cnt -= 1

        if cnt < 0:
            left = max(left, -cnt)

S = "(" * left + S

right = 0
for s in S:
    if s == "(":
        right += 1
    else:
        right -= 1

S = S + ")" * right

print(S)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

cnt = left = 0
for s in S:
    if s == "(":
        cnt += 1
    elif s == ")":
        cnt -= 1

        if cnt < 0:
            left = max(left, -cnt)

S = "(" * left + S

right = 0
for s in S:
    if s == "(":
        right += 1
    elif s == ")":
        right -= 1

S = S + ")" * right

print(S)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#AGC020A
import sys
#import collections

n= int(input())
s= input()
#tmp = input().split()
#s = list(map(lambda a: int(a), tmp))

rcount=0
rcountmax=0
for i in range(0,n):
	if(s[i]==")"):
		rcount+=1
		rcountmax=max(rcountmax,rcount)
	else:
		rcount-=1
lcount=0
lcountmax=0
for i in range(0,n):
	if(s[n-1-i]=="("):
		lcount+=1
		lcountmax=max(lcountmax,lcount)
	else:
		lcount-=1
ans=""
for i in range(0,rcountmax):
	ans+="("
ans+=s
for i in range(0,lcountmax):
	ans+=")"

#print(s)
#print(rcountmax)
#print(lcountmax)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
s=(input())
org=s

while "()" in s:
    s=s.replace("()","")


left=s.count(")")
right=s.count("(")
print("("*left+org+")"*right)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
state = [0]
for s in S:
    state.append(state[-1] + (1 if s == '(' else -1))
ans = - min(state)*'(' + S + (state[-1] - min(state)) * ')'
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

T = S
while "()" in S:
    S = S.replace("()", "")

left = S.count(")")
right = S.count("(")

ans = "(" * left + T + ")" * right

print(ans)

Submission status: Accepted

Solution code:
N, S = open(0).read().split()

cnt = left = 0
for s in S:
    if s == "(":
        cnt += 1
    else:
        cnt -= 1

        if cnt < 0:
            left = max(left, -cnt)

S = "(" * left + S

right = 0
for s in S:
    if s == "(":
        right += 1
    else:
        right -= 1

S = S + ")" * right

print(S)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

cnt = left = 0
for s in S:
    if s == "(":
        cnt += 1
    else:
        cnt -= 1

        if cnt < 0:
            left = max(left, -cnt)

S = "(" * left + S

right = 0
for s in S:
    if s == "(":
        right += 1
    else:
        right -= 1

S = S + ")" * right

print(S)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, itertools


def solve(N: int, S: str):
    c = [0] * N
    counter = 0
    for i in range(N):
        if S[i] == '(':
            counter += 1
        else:
            counter -= 1
        c[i] = counter

    m = min(c)
    if m < 0:
        S = "("*abs(m) + S
        c = list(range(1, abs(m)+1)) + [cc+abs(m) for cc in c]
    
    S = "("*(c[0]-1) + S + ")"*c[-1]
    print(S)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
left = 0
right = 0
left_t = 0
right_t = 0
t = "".join(list(reversed(s)))
for i in range(n):
    if s[i] == ")":
        if left == 0:
            right += 1
        else:
            left -= 1
    if s[i] == "(":
        left += 1
    if t[i] == "(":
        if right_t == 0:
            left_t += 1
        else:
            right_t -= 1
    if t[i] == ")":
        right_t += 1
ans = ("(" * right) + s + ")" * left_t
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
r = 0
l = 0
for s in S:
    if s == "(":
        r += 1
    else:
        if r == 0:
            l += 1
        else:
            r -= 1
ans = "(" * l + S + ")" * r
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
S = input()
ans = deque(S)


while S.find("()") != -1:
    S = S.replace("()","")

for i in range(len(S)):
    if S[i] == ")":
        ans.appendleft("(")
    elif S[i] == "(":
        ans.append(")")
print("".join(ans))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
x=s
while(1):
  a=s.find('()')
  if a==-1:
    break
  s=s[:a]+s[a+2:]
for i in range(len(s)):
  if s[i]==')':
    x='('+x
  else:
    x=x+')'
print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    _, b, c = LS()
    x = int(b[0] + c[0]) % 4
    if not x:
        print("YES")
    else:
        print("NO")
    return

#B
def B():
    II()
    a = LI()
    a.sort()
    print(a[-1]-a[0])
    return

#C
def C():
    II()
    a = LI()
    a = list(map(lambda x: x // 400, a))
    d = defaultdict(int)
    for ai in a:
        d[ai] += 1
    ans1 = 0
    ans2 = 0
    for key, value in d.items():
        if key <= 7:
            ans1 += 1
            ans2 += 1
        else:
            ans2 += value
    if ans1 == 0:
        ans1 = 1
    print(ans1, ans2)
    return

#D
def D():
    n = II()
    s = S()
    ans = deque(s[::1])
    f = 0
    for i in s:
        if i == "(":
            f += 1
        else:
            f -= 1
        if f < 0:
            ans.appendleft("(")
            f += 1
    ans.append(")" * f)
    print("".join(ans))

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
nl = 0
for c in reversed(S):
  if c == "(":
    nl = max(0, nl-1)
  if c == ")":
    nl += 1
nr = 0
for c in S:
  if c == ")":
    nr = max(0, nr-1)
  if c == "(":
    nr += 1
r = "("*nl + S + ")"*nr
print(r)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = input()

stack = deque()
for i in range(n):
    if len(stack) > 0:
        stack_last = stack.pop()
        if stack_last == "(" and s[i] == ")":
            continue
        else:
            stack.append(stack_last)
            stack.append(s[i])
    else:
        stack.append(s[i])

# print(stack)
for i in range(len(stack)):
    if stack[i] == '(':
        s = s + ')'
    else:
        s = '(' + s

print(s)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

l = 0
r = 0
for i in range(N):
    if S[i] == '(':
        r += 1
    else:
        if r > 0:
            r -= 1
        else:
            l += 1
ans = '('*l + S + ')'*r
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,m = LI()
    a = LIR(n)
    ans = 0
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a.sort(key = lambda x:(-1)**i*x[0]+(-1)**j*x[1]+(-1)**k*x[2])
                p = [0,0,0]
                for l in range(m):
                    p[0] += a[l][0]
                    p[1] += a[l][1]
                    p[2] += a[l][2]
                p = abs(p[0])+abs(p[1])+abs(p[2])
                if p > ans:
                    ans = p
    print(ans)
    return

#B
def B():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y,su):
        x = root(x)
        y = root(y)
        su += comb_2(s[x])+comb_2(s[y])
        if rank[x] < rank[y]:
            s[y] += s[x]
            su -= comb_2(s[y])
            par[x] = y
        else:
            s[x] += s[y]
            su -= comb_2(s[x])
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return su

    def comb_2(a):
        return a*(a-1)//2

    n,m = LI()
    v = LIR(m)
    par = [i for i in range(n)]
    rank = [0]*n
    s = [1]*n
    su = comb_2(n)
    ans = [su]
    for a,b in v[:0:-1]:
        a -= 1
        b -= 1
        if root(a) != root(b):
            su = unite(a,b,su)
        ans.append(su)
    for i in ans[::-1]:
        print(i)
    return

#C
def C():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]

    def weight(x):
        root(x)
        return d[x]

    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    d = [0]*n
    for i in range(m):
        l,r,w = LI()
        l -= 1
        r -= 1
        if root(l) != root(r):
            unite(l,r,w)
        else:
            if weight(r)-weight(l) != w:
                print("No")
                return
    print("Yes")
    return

#D
def D():
    h,w = LI()
    n = I()
    a = LI()
    ans = [0]*h*w
    p = 0
    for i in range(n):
        for j in range(a[i]):
            ans[p+j] = i+1
        p += a[i]
    for i in range(h):
        s = ans[i*w:(i+1)*w]
        if i%2:
            print(*s[::-1])
        else:
            print(*s)
    return

#E
def E():
    n,k = LI()
    s = [int(x) for x in input()]
    f = [0]*n
    j = 0
    su = 1
    p = s[0]
    for i in range(1,n):
        if s[i] != p:
            f[j] = su
            j += 1
            su = 1
            p = s[i]
        else:
            su += 1
    f[j] = su
    f.append(0)
    if s[0]:
        m = sum(f[:2*k+1])
        ans = m
        for i in range(2*k+1,n):
            m -= f[i-2*k-1]
            if not i%2:
                m += f[i-1]
                m += f[i]
            ans = max(m,ans)
    else:
        m = sum(f[:2*k])
        ans = m
        for i in range(2*k,n):
            m -= f[i-2*k]
            if not i%2:
                m += f[i]
                m += f[i+1]
            ans = max(m,ans)
    print(ans)
    return

#F
def F():
    n = I()
    a = LI()
    s = [0,0,0]
    for i in a:
        if i%4 == 0:
            s[0] += 1
        elif i%2 == 0:
            s[1] += 1
        else:
            s[2] += 1
    a = [0]
    while 1:
        if s[2]:
            if a[-1] == 2:
                print("No")
                return
            s[2] -= 1
            a.append(2)
            if s[0]:
                s[0] -= 1
                a.append(0)
        elif s[1]:
            if a[-1] == 2:
                print("No")
            else:
                print("Yes")
            return
        else:
            print("Yes")
            return
    return

#G
def G():
    n,m,l = LI()
    r = LI()
    for i in range(l):
        r[i] -= 1
    d = [[float("inf")]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    m = 1<<l
    dp = [[float("inf")]*l for i in range(m)]
    for i in range(l):
        dp[1<<i][i] = 0
    for b in range(m):
        for i in range(l):
            x = r[i]
            if not b&(1<<i):
                continue
            for j in range(l):
                if b&(1<<j):
                    continue
                nb = b|(1<<j)
                y = r[j]
                res = dp[b][i]+d[x][y]
                if res < dp[nb][j]:
                    dp[nb][j] = res
    print(min(dp[m-1]))
    return

#H
def H():
    n,m,q = LI()
    f = [[0]*(n+1) for i in range(n+1)]
    for i in range(m):
        l,r = LI()
        f[l][r] += 1
    for i in range(n+1):
        for j in range(n):
            f[i][j+1] += f[i][j]

    for j in range(n+1):
        for i in range(n):
            f[i+1][j] += f[i][j]
    for i in range(q):
        l,r = LI()
        print(f[r][r]-f[r][l-1]-f[l-1][r]+f[l-1][l-1])
    return

#I
def I_():
    n = I()
    s = input()
    a = ""
    q = 0
    for i in s:
        if i == "(":
            q += 1
        else:
            if q:
                q -= 1
            else:
                a += "("
    print(a+s+")"*q)
    return

#Solve
if __name__ == "__main__":
    I_()

Submission status: Accepted

Solution code:
n=input()
s=input()
t=s
while '()' in s:s=s.replace('()','')
print('('*s.count(')')+t+')'*s.count('('))

Submission status: Accepted

Solution code:

import bisect
import collections
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

n=input()
s=input()

l,r=0,0
for c in s:
    if c == '(':
        r += 1
    else:
        if r:
            r -= 1
        else:
            l += 1
res = "(" * l + s + ")" * r
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
INF = float("inf")


def solve(N: int, S: str):
    X = ""
    counter = 0                 # counterは(の数
    for i, c in enumerate(S):
        if c == ')' and counter == 0:
            X = '(' + X + ')'
        elif c == ')' and counter > 0:
            X = X + ')'
            counter -= 1
        elif c == '(':
            X = X + '('
            counter += 1
    X += ')'*counter
    print(X)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
S = input()
S = S[:-1]
m = 0
diff = 0
for s in S :
    if s == '(' :
        diff += 1
    elif s == ')' :
        diff -= 1
    m = min(m, diff)
print(('('*(-m))+S+(')'*(diff-m)))

Submission status: Accepted

Solution code:
# ABC064D - Insertion
# http://drken1215.hatenablog.com/entry/2019/02/16/080900
def main():
    N = int(input())
    S = input().rstrip()
    l, r = 0, 0
    for i in S:
        if i == "(":
            r += 1
        else:
            if r:
                r -= 1
            else:
                l += 1
    ans = "(" * l + S + ")" * r
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC064D - Insertion
# https://www.hamayanhamayan.com/entry/2017/06/10/224823
def main():
    N = int(input())
    S = input().rstrip()
    cnt, pre = 0, 0
    for i in S:
        if i == "(":
            cnt += 1
        else:
            cnt -= 1
            if cnt < 0:
                pre = max(pre, abs(cnt))
    S = "(" * pre + S
    cnt = 0
    for i in S:
        if i == "(":
            cnt += 1
        else:
            cnt -= 1
    S += ")" * cnt
    print(S)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
c1=0
c2=0
p=10**100
q=10**100
for i in s:
    if i=="(":
        c1+=1
    else:
        c1-=1
    p=min(p,c1)
if p<0:
    s="("*abs(p)+s

for i in range(1,len(s)+1):
    if s[-i]==")":
        c2+=1
    else:
        c2-=1
    q=min(q,c2)
if q<0:
    s=s+")"*abs(q)
print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC64 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(input())
s = input()
cnt = 0
ans = s
while 1:
    f = 0
    for i in range(len(ans)):
        cnt = 0
        for j in range(i+1):
            if ans[j] == ')':
                cnt += 1
        if i+1-cnt < cnt:
            ans = '(' + ans
            f = 1
    if not f:
        break
while 1:
    f = 0
    for i in range(len(ans))[::-1]:
        cnt = 0
        for j in range(i,len(ans))[::-1]:
            if ans[j] == '(':
                cnt += 1
        if len(ans) - i - cnt < cnt:
            ans += ')'
            f = 1
    if not f:
        break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

n_c = 0
min_n_c = 0
for s in S:
    if s == "(":
        n_c += 1
    else:
        n_c -= 1
    min_n_c = min(min_n_c, n_c)
ans = S
for _ in range(-min_n_c):
    ans = "("+ans
for _ in range(n_c-min_n_c):
    ans += ")"

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

cnt = 0
s = ''
for i in range(N):
    if S[i] == '(':
        cnt += 1
    else:
        cnt -= 1
        if cnt < 0:
            s += '('
            cnt = 0
s += S
if cnt:
    s += ')' * cnt

print(s)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())

#処理部分
f = 0
b = 0
count = 0
for i in range(N-1, -1, -1):
    if S[i] == '(':
        if count > 0:
            count -= 1
        else:
            b += 1
    else:
        count += 1

#出力
for i in range(count):
    print ('(', end = '')
for i in S:
    print (i, end = '')
for i in range(b):
    print (')', end = '')
print ()

Submission status: Accepted

Solution code:
N = int(input())
S = input()

left = 0
right = 0

for letter in S:
    if letter == '(':
        left += 1
    if letter == ')':
        right += 1
        if left < right:
            S = '(' + S
            left += 1

if right < left:
    S = S + abs(right - left) * ')'
print(S)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
ok_list = []
min_length = 10**9
for i in range(len(s)+1):
    for j in range(len(s)+1):
        s_part = s
        s_part = ["("] * i + s_part + [")"] * j

        if s_part[0] == "(" and s_part[-1] == ")":
            f = 0
            fmin = 0
            ng = 0
            for k in s_part:
                if k == "(":
                    f += 1
                else:
                    f -= 1
                if f < 0:
                    ng = 1
            if f == 0 and ng == 0:
                ok_list.append("".join(s_part))

minl = min(map(len,ok_list))
ok_list = [ i for i in ok_list if len(i) == minl ]
print(sorted(ok_list)[0])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
s=input().rstrip()
r=0
l=0
for i in s:
    if i=='(':
        r+=1
    else:
        if r>0:
            r-=1
        else:
            l+=1
ans='('*l+s+')'*r
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
a = [0]
for i in range(n):
    if s[i] == "(":
        a.append(a[-1] + 1)
    else:
        a.append(a[-1] - 1)
left = -min(a)
right = a[-1] + left
print("(" * left + s + ")" * right)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cnt = 0
m = 0
for i in s:
    if i == ')':
        cnt += 1
    else:
        cnt -= 1
    m = max(m, cnt)
print('('*m+s+')'*(m-cnt))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
cnt=0
M=0

for i in s:
    if i==")":
        cnt+=1
    else:
        cnt-=1
    M=max(M,cnt)

print("("*M+s+")"*(M-cnt))