Xâu dấu ngoặc gần hợp lệ
Đề bài
Mô tả
Cho một xâu dấu ngoặc độ dài , gồm các kí tự ( và ).
Một xâu dấu ngoặc được gọi là hợp lệ nếu có thể chèn thêm các kí tự 1 và + vào xâu để được một biểu thức số học đúng. Ví dụ, ()() và (()) là các xâu hợp lệ (tương ứng với (1)+(1) và ((1+1)+1)), trong khi )( và ( thì không.
Bạn được phép đổi loại của đúng một kí tự trong xâu: nếu kí tự đó là ( thì biến thành ) và ngược lại.
Hãy đếm số vị trí () sao cho sau khi đổi loại của , xâu thu được là một xâu dấu ngoặc hợp lệ.
Dữ liệu vào
- Dòng đầu chứa một số nguyên — độ dài xâu dấu ngoặc.
- Dòng thứ hai chứa xâu độ dài chỉ gồm kí tự
(và).
Dữ liệu ra
In ra một số nguyên duy nhất — số vị trí thỏa mãn yêu cầu đề bài.
Ràng buộc
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 (((()) |
3 | Đổi vị trí 2 cho ()(()), đổi vị trí 3 cho (()()), đổi vị trí 4 cho ((())) — đều hợp lệ. Có vị trí phù hợp. |
| 6 ()()() |
0 | Xâu đã hợp lệ, mọi phép đổi đều phá vỡ tính hợp lệ. |
| 1 ) |
0 | Độ dài là số lẻ nên không thể tạo thành xâu hợp lệ. |
| 8 )))((((( |
0 | Không tồn tại phép đổi đơn lẻ nào biến xâu này thành hợp lệ. |
Bình luận