## CEOI '22 P2 - Homework

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Little Helena recently finished her first year of primary school. She is a model student, has straight A's, and has a huge passion for mathematics. She is currently on a well-deserved vacation with her family, but she's starting to miss her daily homework. Luckily, her older brother decided to quench her intellectual thirst, and gave her the following problem.

A valid expression is defined recursively as follows:

• the string ? is a valid expression which represents a number.
• if and are valid expressions, then so are and , where the former represents a function returning the smaller of its two arguments, while the latter represents a function returning the larger of its two arguments.

For example, expressions and are valid according to the definition above, but expressions , and are not.

Helena is given a valid expression containing a total of question marks. Each question mark is to be replaced with a number from the set in such a way that each number from this set appears exactly once in the expression. In other words, the question marks are replaced by a permutation of the numbers from to .

Once the question marks have been replaced by numbers, the expression can be evaluated and its value will be an integer between and . Considering all the ways of assigning numbers to question marks, how many different values can Helena obtain after evaluating the expression?

#### Input Specification

The first and only line contains a single valid expression.

#### Output Specification

Output a single integer between and , the number of different values obtainable by evaluating the expression.

#### Constraints

Each function in the expression has at least one question mark as an argument.

#### Sample Input 1

min(min(?,?),min(?,?))

#### Sample Output 1

1

#### Explanation for Sample 1

No matter how the numbers are assigned, the value of the resulting expression will always be equal to the minimum of the set , which is . Therefore, there is only one possible value.

#### Sample Input 2

max(?,max(?,min(?,?)))

#### Sample Output 2

2

#### Explanation for Sample 2

The numbers and can be obtained as and . It can be shown that values and are not attainable and so the answer is .

#### Sample Input 3

min(max(?,?),min(?,max(?,?)))

#### Sample Output 3

3