Dãy ngoặc hỏng
Đề bài
Mô tả
Cho một dãy ngoặc độ dài , chỉ gồm hai kí tự "(" và ")".
Một dãy ngoặc được gọi là đúng nếu:
- Dãy rỗng là đúng;
- Nếu là dãy đúng thì "(" + + ")" cũng là dãy đúng;
- Nếu và là hai dãy đúng thì (nối liền nhau) cũng là dãy đúng.
Ví dụ "(()())" và "()" là các dãy đúng, còn ")(" và "())" thì không.
Bạn được phép thực hiện nhiều nhất một thao tác: chọn một kí tự ngoặc bất kì rồi di chuyển nó tới một vị trí bất kì khác trong dãy (không được đổi chiều ngoặc, tức không được biến "(" thành ")" hay ngược lại).
Hãy xác định xem có thể làm cho dãy trở thành dãy ngoặc đúng bằng nhiều nhất một thao tác di chuyển hay không.
Dữ liệu vào
- Dòng thứ nhất chứa số nguyên — độ dài của dãy.
- Dòng thứ hai chứa dãy ngoặc độ dài gồm các kí tự "(" và ")".
Dữ liệu ra
In ra "Yes" nếu có thể biến dãy thành dãy ngoặc đúng bằng nhiều nhất một thao tác di chuyển, ngược lại in ra "No".
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 )( |
Yes | Di chuyển ngoặc đầu tiên xuống cuối dãy để được "()", là dãy ngoặc đúng. |
| 3 (() |
No | Số ngoặc mở và ngoặc đóng không bằng nhau nên không thể tạo thành dãy đúng. |
| 2 () |
Yes | Dãy đã đúng sẵn, không cần di chuyển. |
| 10 )))))((((( |
No | Dù di chuyển một ngoặc cũng không thể sửa được dãy lệch quá nhiều. |
Bình luận