CEOI '22 P2 - Homework

View as PDF

Submit solution

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 A and B are valid expressions, then so are \min(A, B) and \max(A, B), 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 \min(\min(?,?), \min(?,?)) and \max(\max(?,?), \min(?,?)) are valid according to the definition above, but expressions ??, \max(\min(?)) and \min(?,?,?) are not.

Helena is given a valid expression containing a total of N question marks. Each question mark is to be replaced with a number from the set \{1, 2, \dots, N\} 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 1 to N.

Once the question marks have been replaced by numbers, the expression can be evaluated and its value will be an integer between 1 and N. 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 1 and N, the number of different values obtainable by evaluating the expression.

Constraints

For all subtasks:

2 \le N \le 1\,000\,000

Subtask Score Constraints
1 10 N \le 9
2 13 N \le 16
3 13 Each function in the expression has at least one question mark as an argument.
4 30 N \le 1\,000
5 34 No additional constraints.

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 \{1, 2, 3, 4\}, which is 1. Therefore, there is only one possible value.

Sample Input 2

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

Sample Output 2

2

Explanation for Sample 2

The numbers 3 and 4 can be obtained as 4 = \max(4, \max(3, \min(2, 1))) and 3 = \max(3, \max(2, \min(1, 4))). It can be shown that values 1 and 2 are not attainable and so the answer is 2.

Sample Input 3

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

Sample Output 3

3

Comments

There are no comments at the moment.