Con quái vật
Đề bài
Mô tả
Một xâu chỉ gồm các dấu ngoặc tròn '(' và ')' được gọi là dãy ngoặc đúng nếu nó được xây dựng theo các quy tắc sau:
- Xâu rỗng là một dãy ngoặc đúng.
- Nếu là dãy ngoặc đúng thì cũng là dãy ngoặc đúng.
- Nếu và là các dãy ngoặc đúng thì xâu ghép cũng là dãy ngoặc đúng.
Cho một xâu gồm các ký tự '(' , ')' và '?'. Một xâu như vậy được gọi là đẹp nếu tồn tại một cách thay thế mỗi dấu '?' bằng '(' hoặc ')' sao cho xâu thu được là một dãy ngoặc đúng khác rỗng.
Hãy đếm số cặp chỉ số với sao cho xâu con là xâu đẹp.
Dữ liệu vào
Một dòng duy nhất chứa xâu gồm các ký tự '(' , ')' và '?'.
Dữ liệu ra
In ra một số nguyên duy nhất, là số cặp thỏa mãn.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| ((?)) | 4 | Bốn xâu con đẹp: "(?" → "()", "?)" → "()", "((?)" → "(())", "(?))" → "(())". |
| ??()?? | 7 | Bảy xâu con đẹp, chẳng hạn "??" → "()", "?()?" → "(())", "??()??" → "()()()". |
Bình luận