Decision Non-Making Tree

Decision Non-Making Tree

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

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

Time limit: 1 second
Memory limit: 256 megabytes

Decision trees are often used in machine learning. Each internal vertex of such a tree corresponds to some question, and each edge corresponds to the choice of an answer (yes/no). In this way, with a few questions, the input data can be split into a fairly large number of classes. Dima's latest project is a decision non-making tree. Its structure is similar to that of a decision tree. It is a complete binary tree of depth $n$. Every vertex, except the vertices of the last level, stores a number $p$ ($0 \leqslant p \leqslant 100$). This number is the probability of the choice: with probability $p$ per cent the algorithm chooses to go left and, accordingly, with probability $100 - p$ per cent it goes right.

Let us agree to denote a move to the left by the digit 0 and a move to the right by the digit 1. Thus, each vertex of the bottom level corresponds to a binary string of length $n$ (the sequence of decisions from the root to the leaf).

The probability of obtaining this string equals the product of the probabilities of all the choices made on the path from the root to the leaf.

Dima has already written a structure for such a tree and wants to test it. For this, he created a tree of depth 3. So it has 7 internal vertices in total. Each vertex has its own number $p$. The layout of these vertices is shown below:

[Figure: the layout of the vertices; see page 2 of the original PDF. Transcription: internal vertices 1–7, edges labelled 0 (left) and 1 (right), leaves labelled with their binary strings.]

              (1)
         0 /       \ 1
      (2)             (3)
   0 /   \ 1       0 /   \ 1
  (4)     (5)     (6)     (7)
 0/ \1   0/ \1   0/ \1   0/ \1
000 001 010 011 100 101 110 111

Find the probabilities of all binary strings of length 3 and output the strings in non-decreasing order of probability. If probabilities are equal, the strings must be output in lexicographic order.

Input format

The first line contains 7 integers $p$ ($0 \leqslant p \leqslant 100$): the probabilities for the vertices, as shown in the figure.

Output format

Output 8 lines. Each line must contain a binary string of length 3. The strings must be in non-decreasing order of probability. If probabilities are equal, the strings are compared lexicographically.

Examples

Standard input:

40 90 20 90 100 70 0

Standard output:

011
110
001
101
010
100
000
111

Note

In the first test example, the binary strings have the following probabilities:

• 011 – 0.0
• 110 – 0.0
• 001 – 0.036
• 101 – 0.036
• 010 – 0.04
• 100 – 0.084
• 000 – 0.324
• 111 – 0.48

Scoring criterion: exact match of the answer — 100 points

Maximum score for the task — 100