Free Bracket

View as PDF

Submit solution

Points: 1.14 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
ACM Jakarta 2008
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 các cách đặt khác nhau bạn có thể 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 \le 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 ~\le 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.

Giới hạn

Có ~50\%~ số test ~N \le 10~

Sample Input

1-2+3-4-5
38+29-91
54-18+22+74

Sample Output

6
1
3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.