LKNGOAC - Liệt kê cặp dấu 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
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho dãy ngoặc đúng gồm ~n~ dấu mở ngoặc ( và ~n~ dấu đóng ngoặc ). Các dấu ngoặc được đánh số thứ tự từ ~1~ đến ~2n~. Hãy liệt kê chỉ số của các cặp dấu mở ngoặc và đóng ngoặc tương ứng.
Input
- Gồm một dòng duy nhất chứa xâu ký tự biểu diễn dãy ngoặc.
Giới hạn:
- ~1 ≤ n ≤ 10^5~.
Output
- Gồm ~n~ dòng, mỗi dòng gồm hai số ~u, v~ là chỉ số của các cặp ngoặc tương ứng nhau, thứ tự liệt kê tăng dần theo chỉ số của dấu ngoặc đóng.
Sample
Input #1
()(()())
Output #1
1 2
4 5
6 7
3 8
Problem source: Chuyên Sơn La Online Judge
Bình luận
ý tưởng của mình là các bạn cứ gặp kí tự '(' thì thêm chỉ số thứ tự vào ngăn xếp , ngược lại nếu gặp ')' thì sẽ in ra đầu ngăn xếp và vị trí hiện tại ... Như ví dụ trên : i=0 =>s[i]='(' => stack thêm 1 i=1 =>s[i]=')'=>lấy ra phần tử cuối cùng stack và in vị trí hiện tại ,rồi xóa thằng 1 đi . i=2=>s[i]='(' =>stack thêm 3 i=3=>s[i]='('=>stack thêm 4 i=4 =>s[i]=')'=>ấy ra phần tử cuối cùng stack và in vị trí hiện tại ,rồi xóa thằng 4 đi.(stack vẫn còn thằng 3) ... cứ làm như thế thì sẽ đc các dấu đóng mở ngoặc tương ứng .