TopCoder problem "CountExpressions" used in SRM 398 (Division I Level One , Division II Level Two)



Problem Statement

    

You are helping your brother with his homework assignment. His teacher gave him two distinct numbers x and y, and asked him to use those numbers to form as many different expressions as possible. Each expression must satisfy all of the following rules:

  1. The only allowed operators are '+', '-' and '*'.
  2. x and y must each appear exactly twice. No other numbers are allowed.
  3. The result of the expression must be equal to val.



In other words, each expression can be written in the form "a op1 b op2 c op3 d", where each of op1, op2 and op3 is '+', '-' or '*', and among the numbers a, b, c and d, exactly two are equal to x and the other two are equal to y. Please note that the unary minus is not allowed (see example 0). Expressions are calculated from left to right, and there is no operator precedence. For example, to calculate the result of "2 + 2 * 3 + 3", you would first calculate 2 + 2, then multiply the result by 3, and then add 3 to get 15.



Return the total number of different expressions that can be formed. Two expressions are considered different if their string notations (as described in the previous paragraph) are different. For example, the expressions "2 + 3 - 2 - 3", "2 - 2 + 3 - 3" and "2 - 3 - 2 + 3" are all different.

 

Definition

    
Class:CountExpressions
Method:calcExpressions
Parameters:int, int, int
Returns:int
Method signature:int calcExpressions(int x, int y, int val)
(be sure your method is public)
    
 

Constraints

-x and y will each be between -100 and 100, inclusive.
-x and y will be different.
-val will be between -100000000 and 100000000, inclusive.
 

Examples

0)
    
7
8
16
Returns: 9
The possible expressions are: 
8 + 8 + 7 - 7
8 + 7 + 8 - 7
7 + 8 + 8 - 7
8 + 8 - 7 + 7
8 + 7 - 7 + 8
7 + 8 - 7 + 8
8 - 7 + 8 + 7
8 - 7 + 7 + 8
7 - 7 + 8 + 8
Please note that the unary minus is not allowed, so "-7 + 7 + 8 + 8" is not a valid expression.
1)
    
3
5
7
Returns: 5
The possible expressions are:

3 * 5 - 3 - 5
5 * 3 - 3 - 5
3 * 5 - 5 - 3
5 * 3 - 5 - 3
5 - 3 * 5 - 3
2)
    
99
100
98010000
Returns: 6
3)
    
-99
42
-1764
Returns: 2
-99 - (-99) - 42 * 42
-99 - 42 - (-99) * 42
4)
    
100
-100
-100000000
Returns: 0
There are no valid expressions.
5)
    
1
2
5
Returns: 17

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8157

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12170&pm=8157

Writer:

boba5551

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Simple Math