Programming contests

ECN selejtező programozó csapatverseny, 2015. április 19.

April 19, 2015 10:10 AM – April 19, 2015 3:10 PM

Free Parentheses

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 resulting values 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

Input Specification

There will be several expressions in the input. Each expression is written in one line. The expression consists of only N (2 ≤ N ≤ 30) nonnegative numbers less than 100, separated by addition or subtraction operators. There will be no operator before the first number.

Output Specification

For each expression, print the number of different values that can be derived from the expression by adding any number of parentheses.

Sample Input

  1. 1 - 2 + 3 - 4 - 5
  2. 38 + 29 - 91
  3. 54 - 18 + 22 + 74
download as text file

Output for Sample Input

  1. 6
  2. 1
  3. 3
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019