Gửi bài giải
Điểm:
1,29 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Xét dãy ngoặc chỉ gồm các ngoặc vuông và tròn ~-~ '() []'.
Dãy ngoặc hợp lệ là:
- '()', '[]': hợp lệ.
- ~A~ hợp lệ thì ~(A)~ và ~[A]~ hợp lệ.
- ~A~, ~B~ hợp lệ thì AB hợp lệ.
Ví dụ: '() () []', '([]) [()]' và '[(())] []' hợp lệ. Còn '(', '] [', '[(]' and '([)]' không hợp lệ.
Cho ~1~ dãy ngoặc. Ở mỗi bước chèn thêm ngoặc vuông hoặc tròn vào đầu hoặc cuối. Với mỗi bước tính độ dài dãy ngoặc hợp lệ ngắn nhất gồm các ngoặc liên tiếp nhau mà chứa ngoặc mới được thêm vào.
Input
Dòng đầu là dãy ngoặc ban đầu, độ dài ~\le 100\,000~. Dòng tiếp theo là số nguyên ~N~, ~1 \leq N \leq 100\,000~, số thao tác.
~N~ dòng tiếp theo, mỗi dòng gồm số nguyên ~A~ và kí tự ~C~.
- ~A = 0~ thì ~C~ được chèn vào đầu xâu.
- ~A = 1~ thì ~C~ được chèn vào cuối xâu.
Output
Với mỗi bước ~i~, ~1 \le i \le N~, ghi độ dài ngắn nhất tìm được trên ~1~ dòng.
Sample Input 1
[])
3
0 )
0 (
0 (
Sample Output 1
0
2
6
Sample Input 2
(]
3
1 )
0 )
0 (
Sample Output 2
0
0
2
Bình luận