Dãy ngoặc
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (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
Cho 1 xâu ~s~ có độ dài n gồm các kí tự
), ( và ?. Gọi ~x~ là số cách thay thế các dấu ? trong xâu để tạo thành 1 dãy ngoặc đúng. In ra ~\min(x, 10)~.
Dãy ngoặc đúng được định nghĩa như sau:
Xâu rỗng là dãy ngoặc đúng
Nếu ~s~ là một dãy ngoặc đúng, ~\texttt{(} + s + \texttt{)}~ cũng là một dãy ngoặc đúng
Nếu ~s_1~ và ~s_2~ là hai dãy ngoặc đúng, ~s_1 + s_2~ cũng là một dãy ngoặc đúng
Input
Dòng đầu tiên chứa 1 số nguyên dương ~t~ (~t \le 10^5~) là số lượng bộ test.
Mỗi bộ test bao gồm duy nhất 1 dòng là xâu ~s~.
Tổng độ dài xâu ~s~ trong các bộ test không vượt quá ~10^5~.
Output
Với mỗi bộ test, in ra ~\min(x, 10)~.
Sample Input 1
10
)(??
)(((
())?
))?)
?(?)
?)?(
???)
((?)
)?()
))?(
Sample Output 1
0
0
0
0
1
0
2
1
0
0
Bình luận