Mock CCC '19 Contest 1 J4 - Balance Brackets

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Ninjaclasher cannot stand unbalanced brackets. An example of an unbalanced bracket is (() or )(). Your job is to insert some amount of ( or ) into the sequence of brackets in order to balance it.

A balanced bracket is a pair of brackets such that ( is completed by ). Examples of balanced brackets are (), (()), and (()()).

You are to find the shortest balanced bracket sequence that can be obtained. If there is more than one such sequence, then output the lexicographically smallest one.

Note: we compare lexicographically smaller such that ( < ).

Constraints

  • 1 \le N \le 100, N is the size of the initial sequence given
  • \left | S \right | = N, \left | S \right | is the size of the sequence
  • S may only consist of the characters ( and ).

Input Specification

The first line of input will contain a single integer, N.

The second line of input will contain a sequence of characters ( and ), S.

Output Specification

Output, on a single line, the lexicographically smallest balanced bracket sequence that can be made.

Sample Input 1

6
(()(((

Sample Output 1

(()((())))

Sample Input 2

9
))()()))(

Sample Output 2

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

Comments

There are no comments at the moment.