Bedao Mini Contest 09 - BRACKET

Xem dạng PDF

Gửi bài giải


Điểm: 0,40 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -27
    htrung1105  đã bình luận lúc 15, Tháng 4, 2022, 9:38

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.