Special Decision Tree

Special Decision Tree

English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email [email protected].

Task 7 of the school stage (Moscow) of the All-Russian School Olympiad (VsOSh) 2025/26 in artificial intelligence, grades 9–11. Original: tasks-ai-9-11-sch-msk-25-26.pdf.

Special decision tree

Input file name: standard input
Output file name: standard output
Time limit: 1 second
Memory limit: 256 megabytes

You are given a complete binary decision tree of depth $n$. Exactly $n$ steps are taken from the root to a leaf. At each step, one of two decisions is made: go left or go right. Initially, both options are equally likely: each edge has probability $1/2$.

Someone modified the tree and changed two edge probabilities to 0:

• the first edge is the $a$-th edge on the "always left" path (the edge between levels $a - 1$ and $a$ if you choose left at every step from the root);
• the second edge is the $b$-th edge on the "always right" path (the edge between levels $b - 1$ and $b$ if you choose right at every step from the root).

All the other edges still have probability $1/2$ (except for the edges that have lost their neighbouring edge: their probability is now equal to one).

The outcomes in this tree are its leaves (the vertices on the very bottom level). The probability of each outcome is the product of the probabilities along the path to the corresponding leaf.

You need to determine how many different outcomes (leaves of the tree) still have non-zero probability.

Input format

The only line contains three integers $n$, $a$, $b$ ($1 \le n \le 60$, $1 \le a, b \le n$).

Output format

Output one integer: the number of leaves that remain reachable (that is, that correspond to paths of non-zero probability).

Note

[Figure: see page 3 of the original PDF. Transcription: a complete binary tree of depth 3 in which the edge from the root to its right child and the edge from the root's left child to its own left child are crossed out in red. Of the eight leaves, the third and fourth from the left are green (reachable); the other six are red and marked with a cross.]

In the first test example, only 2 outcomes remain reachable.

Translator's note: the paper does not print the test examples themselves.

Translator's note: the statement paper gives only the total for the olympiad (112 points), and the official solutions state no points for this task; the total minus the maxima of the other seven tasks (92 points) leaves 20.