You are given a simple arithmetic expression which consists of only addition and subtraction operators. For example:
1 - 2 + 3 - 4 - 5
You are free to put any parentheses to the expression anywhere you want and as many as you want. However it should be a valid expression after you put the parentheses. The question is how many different numbers can you make? For example, adding parentheses to the above expression can give you 6 different values:
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
There will be many expressions in the input. Each expression is written in one line. The expression consists of only N
$(2 \le N \le 30)$
-->
(2
SRC="/ntujudge/problemdata/633.png"
ALT="$ \le$">N
SRC="/ntujudge/problemdata/633.png"
ALT="$ \le$">30)
For each expression, print the number of different values that can be derived from the expression by adding any number of parentheses.
1 - 2 + 3 - 4 - 5
38 + 29 - 91
54 - 18 + 22 + 74
6
1
3
Migrated from old NTUJ.
ACM ICPC regional Jakarta site 2008
| No. | Testdata Range | Score |
|---|