Problems
6. PlusMinus
Number GameStuart von Chritijan's teacher has given him a puzzle. She gave him a sequence of N numbers and asked him to place '+' OR '-' symbols between adjacent numbers such that the entire expression sums to ZERO. Stuart, being an ace puzzle solver, solved it in a jiffy. He now ponders over how many ways there are to solve the puzzle. Alas, this is too tough for him. Help him out!
Input Format:
- Line 1 : A single integer T, the number of testcases.
- This is followed by T test cases.
- Each test case consists of 2 lines.
- The first line contains N, the number of integers.
- The second line contains N integers : a_1, a_2, a_3, ..., a_n.
Output Format:
For each test case print a single integer giving the number of ways you can place + OR - symbols between a1, a2, ..., an such that the sum adds up to 0.
Constraints:
1 <= T <= 15
1 <= N <= 30
a_i fits in a 32-bit signed integer(int).
Points:
400
Scoring:
Absolute Score = 1000000 / ( 5*S + 2*C + 10*K + 3*O )
where,
S = Number of semicolons ;
C = Number of non-whitespace characters
K = Number of keywords
O = Number of commas ,
Allowed Header files:
stdio.h
stdlib.h
Sample Input:
1
3
1 2 3
Sample Output:
1
Explanation:
1+2-3=0
However, -1-2+3 is not valid because you can place the operators only in between two adjacent numbers, i.e. , no operator can be placed before the first number in the sequence.