6÷2(1+2)
Time limit8sMemory limit512 MB
Count the distinct integer results obtainable by parenthesizing an expression in any order, with integer division truncated toward zero and division by zero treated as invalid.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Brute force, Math, Implementation
- Solved
- No attempts yet
Problem
Kitamasa is a mathematics student. He is very good at mathematics but not so good at arithmetic. He is especially bad with operator precedence: he understands that parentheses must be evaluated first, but he cannot remember whether "+" or "*" takes priority, nor whether a run of operators should be evaluated from the left or from the right, so he evaluates them in whatever order he feels like at the moment. For example, for the expression "1*1-1+1" he sometimes evaluates from the front as "((1*1)-1)+1", and sometimes even from the middle as "(1*(1-1))+1". He is also bad with fractions and decimals, so in division he always rounds toward the smaller absolute value, discarding the fractional part to get an integer. When the divisor is zero, Kitamasa assumes he made a mistake somewhere and starts the whole calculation over from the beginning.
Kitamasa claims that no matter what order he calculates in, the final result is the same. To show that this is wrong, you must write a program that, for a given expression, finds how many distinct results Kitamasa's calculation can produce. Different evaluation orders that yield the same final answer count as one. It is guaranteed that for each given expression at least one evaluation order produces no division by zero, and that for every evaluation order the result and every intermediate value have absolute value at most 10^9.
Input
The input consists of one or more lines, each containing one expression. The grammar of expressions is given by the following BNF.
<expr> ::= <num>
| "(" <expr> ")"
| <expr> "+" <expr>
| <expr> "-" <expr>
| <expr> "*" <expr>
| <expr> "/" <expr>
<num> ::= <digit> | <num> <digit>
<digit> ::= "0" | "1" | "2" | "3" | "4"
| "5" | "6" | "7" | "8" | "9"
Every expression follows these grammar rules. Each input line is at most 200 characters long. An expression contains at most 10 operators ("+", "-", "*", "/").
The end of the input is indicated by a line consisting of a single "#".
Output
For each expression, print how many distinct results Kitamasa's calculation can produce. Print one line per expression.