CountExpressions
SRM 398 · 2008-04-15 · by boba5551
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:
- The only allowed operators are '+', '-' and '*'.
- x and y must each appear exactly twice. No other numbers are allowed.
- 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.
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.
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.
100 1 10000 Returns: 12
-100 100 2 Returns: 0
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
34 67 95 Returns: 0
-99 42 -1764 Returns: 2
-99 - (-99) - 42 * 42 -99 - 42 - (-99) * 42
100 -100 -100000000 Returns: 0
There are no valid expressions.
Submissions are judged against all 58 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CountExpressions with a public method int calcExpressions(int x, int y, int val) · 58 test cases · 2 s / 256 MB per case