Nội dung Bài tập
- Mã:
- DAYNGOAC
- Tên:
- Dãy ngoặc
- Dạng thi:
- acm
- Thang điểm:
- 1 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- trumpfan
Trumpfan rất yêu thích các dãy ngoặc "đúng". Dãy ngoặc "đúng" là chuỗi mà các ký tự gồm '(' hoặc ')', tổng số ngoặc mở bằng tổng số ngoặc đóng và mỗi ngoặc mở có tương ứng một ngoặc đóng ở vị trí sau nó. Ví dụ một số dãy ngoặc đúng là "", "()", "(())", và "()()".
Với 2 chuỗi S, T cho trước ta có LCS(S, T) = dãy con chung dài nhất của 2 chuỗi S và T. Ví dụ: LCS("abcde", "bad") = 2.
Cho trước dãy ngoặc đúng S. Trumpfan muốn đếm xem có bao nhiêu dãy ngoặc đúng T thỏa mãn:
+ Có cùng độ dài với S.
+ T là dãy ngoặc "đúng".
+ T phải khác S.
+ LCS(T, S) lớn nhất có thể.
Bạn hãy giúp Trumpfan nhé.
Input
Gồm nhiều dòng, mỗi dòng chứa một chuỗi ngoặc S. (4 <= độ dài S <= 50).
Output
Gồm nhiều dòng ứng với các test, mỗi dòng in ra số lượng chuỗi thỏa mãn đề bài
Examples
input
(())()
output
3
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...