NLP

NLP

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

All-Russian School Olympiad in Informatics 2025–2026, Regional Stage, Grades 9–11
“Artificial Intelligence” profile, Tour 1, 17 January 2026
Task F

Points for the task: 50
Answer submission format: entering the answer
Number of attempts: 10
Submission that counts: the last one

Statement

Petya is studying a language whose alphabet consists of the letters

$$\{A, D, E, I, L, M, N, S, T\}.$$

Initially, the word $DS$ is written.

Then, at each step, one more letter is appended to the word on the right.

The choice of the new letter depends only on the last letter of the current word.

The rules for appending a new letter are as follows:

• If the last letter is $A$, one of $\{M, D\}$ is appended with equal probability.
• If the last letter is $E$ or $I$, one of $\{T, S, M\}$ is appended with equal probability.
• If the last letter is $T$ or $M$, one of $\{L, N\}$ is appended with equal probability.
• If the last letter is $N$ or $D$, one of $\{A, I\}$ is appended with equal probability.
• If the last letter is $S$ or $L$, one of $\{E, I, D\}$ is appended with equal probability.

Petya is a very keen gambler. He is waiting for the substring $ML$ to appear in the string. Find the expected number of steps (that is, of appended letters) needed for this to happen.

Output format

Round the answer to 2 decimal places, using a point as the decimal separator.

Scoring

An exact match of the answer: 50 points.

Test results are not available during the tour.