C11FBR - Free Bracket
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho dãy các phép tính số học chỉ gồm các phép cộng trừ các số nguyên không âm. Ví dụ :
- 1 – 2 + 3 – 4 – 5
Bạn được phép đặt các dấu ngoặc ‘(‘, ‘)’ vào dãy phép tính mà ko được thay đổi các dấu cộng trừ. Với mỗi cách đặt bạn sẽ được các kết quả khác nhau. Ví dụ :
- 1 - 2 + 3 - 4 - 5 = -7
- 1 - (2 + 3 - 4 - 5) = 5
- 1 - (2 + 3) - 4 - 5 = -13
- 1 - 2 + 3 - (4 - 5) = 3
- 1 - (2 + 3 - 4) - 5 = -5
- 1 - (2 + 3) - (4 - 5) = -3
Câu hỏi đặt ra cho bạn là có bao nhiêu giá trị khác nhau có thể nhận được bằng cách đặt các dấu ngoặc vào dãy phép tính như trên?
Input
Mỗi test gồm 5 test nhỏ, mỗi test nhỏ là 1 dãy phép tính gồm N số nguyên ko âm (N <= 30) được ghi trên 1 dòng, các số được nối bởi dấu cộng hoặc trừ. Không có dấu trừ ở đầu dãy và không có dấu cách. Các số trong test <= 100.
Output
Với mỗi bộ test ghi ra số lượng giá trị khác nhau nhận được bằng cách thêm dấu ngoặc vào dãy phép tính. Kết quả mỗi bộ test in trên 1 dòng.
Chú ý
Có 50% số test N <= 10
Example
Input: 1-2+3-4-5
38+29-91
54-18+22+74
Output: 6
1
3
- Người up: yenthanh132
- Nguồn bài: ACM Jakarta 2008