Bedao Mini Contest 09 - BRACKET

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

~Mike~ đi du lịch nước ~Pa~ và mua được một dãy ngoặc đúng rất đẹp.

Một dãy ngoặc đúng được định nghĩa như sau:

  • Xâu rỗng là ~1~ dãy ngoặc đúng.
  • Nếu ~A~ là ~1~ dãy ngoặc đúng thì ~(A)~ là ~1~ dãy ngoặc đúng.
  • Nếu ~A~ và ~B~ là ~2~ dãy ngoặc đúng thì ~AB~ là ~1~ dãy ngoặc đúng.

~Mike~ dự định khi về nhà sẽ đem khoe với mọi người, tuy nhiên một quả tên lửa không biết của ai từ trên trời rơi đã xuống và làm bay mất một vài dấu ngoặc và chỉ còn lại đúng ~n~ dấu ngoặc trong dãy.

Dù không bị thương nhưng ~Mike~ vẫn rất buồn vì dãy ngoặc đã bị mất đi vẻ đẹp vốn có của nó, bạn hãy giúp ~Mike~ khôi phục lại vẻ đẹp ấy bằng cách chèn vào số lượng ít nhất các dấu ngoặc sau cho dãy ngoặc ấy vẫn trở thành một dãy ngoặc đúng nhé!!!

Lưu ý: Đề bài luôn đảm bảo tồn tại ít nhất một đáp án thỏa mãn.

Input

  • Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \leq 10^5)~.

  • Dòng thứ hai chứa ~n~ kí tự miêu tả dãy ngoặc.

Output

In ra dãy ngoặc đúng với số lần chèn ít nhất. Nếu có nhiều dãy ngoặc thỏa mãn, in ra một dãy bất kì.

Sample Input 1

2
)(

Sample Output 1

()()

Sample Input 2

3
(()

Sample Output 2

(())

Subtask

  • ~20\%~ số test có ~n \leq 100~

  • ~20\%~ khác có ~n \leq 1000~

  • ~60\%~ còn lại không có ràng buộc gì thêm


Comments

Please read the guidelines before commenting.