# Regional Stage 2025–2026, Tour 1: Full Paper
*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*
All-Russian School Olympiad in Informatics 2025–2026, Regional Stage, Grades 9–11
“Artificial Intelligence” profile, Tour 1, 17 January 2026
---
## A. Natural Numbers
**Points for the task:** 50
**Answer submission format:** entering the answer
**Number of attempts:** 10
**Submission that counts:** the last one
### Statement
One hundred natural numbers were written in a row, one after another. The second number was equal to 1, and each number, starting from the third, is equal to the sum of all the numbers written before it. Then the first number was erased. It turned out that one of the remaining numbers is equal to 123456123456123456. What could the erased number have been?
### Output format
As your answer, output all suitable values **in ascending order**, separated by spaces.
### Scoring
An exact match of the answer: 50 points.
Test results are **not available** during the tour.
---
## B. Matrices and Forgotten Activations
**Points for the task:** 50
**Answer submission format:** entering the answer
**Number of attempts:** 10
**Submission that counts:** the last one
### Statement
Vasya is learning to draw pictures with a neural network: he wants to map each point of the plane to a pixel colour in three channels (R, G, B).
The network receives as input the vector
$$
x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix},
$$
and then performs the same operation several times in a row: it multiplies the current column vector by a weight matrix and obtains a new column vector. The sizes of the vectors obtained one after another inside the network are:
$$
2 \to 256 \to 128 \to 64 \to 3,
$$
where $2$ is the size of the input vector and $3$ is the size of the output vector.
Through carelessness, Vasya forgot to add everything “interesting” to the network: both the addition of constants and the non-linear functions. Therefore, all the work of the network up to the last step consists only of successive multiplications by matrices. Denote by
$$
T(x_1, x_2)
$$
the three-dimensional vector obtained at the very last layer before the final processing.
Vasya obtains the actual pixel colour after clipping the result coordinate-wise to the range from $0$ to $255$:
$$
\operatorname{clip}(y)_i =
\begin{cases}
0, & y_i < 0,\\
y_i, & 0 \le y_i \le 255,\\
255, & y_i > 255,
\end{cases}
$$
and, finally,
$$
f(x_1, x_2) = \operatorname{clip}(T(x_1, x_2)).
$$
In an experiment with the network weights already trained, it turned out that
$$
f(-2, 3) = \begin{pmatrix} 60 \\ 40 \\ 100 \end{pmatrix},
\qquad
f(1, 3) = \begin{pmatrix} 200 \\ 50 \\ 80 \end{pmatrix}.
$$
Find the vector $f(-7, 6)$.
### Output format
As your answer, output three numbers separated by spaces. If a number turns out to be non-integer, output it with a precision of 6 decimal places. If there is no answer, or if several answers are possible, output -1.
### Scoring
An exact match of the answer: 50 points.
Test results are **not available** during the tour.
---
## C. Mean and Median
**Points for the task:** 50
**Answer submission format:** entering the answer
**Number of attempts:** 10
**Submission that counts:** the last one
### Statement
Let $x_1, \dots, x_{10} \in [0, 1]$, and let the following conditions hold:
$$
|x_i - x_j| \ge 0.01 \quad \text{for all } i \ne j,
$$
and every subsegment $[a, a + 0.25] \subset [0, 1]$ contains at least one point of the set $\{x_1, \dots, x_{10}\}$.
Sort the numbers:
$$
x_{(1)} \le x_{(2)} \le \dots \le x_{(10)}.
$$
Denote by
$$
\overline{x} = \frac{1}{10} \sum_{k=1}^{10} x_{(k)}, \qquad
m = \frac{x_{(5)} + x_{(6)}}{2}
$$
the mean and the median (taken as the mean of the two middle numbers in order).
By how much at most can the mean $\overline{x}$ differ from the median $m$? That is, find
$$
\max |\overline{x} - m|
$$
under the conditions described.
### Output format
Round the answer to 6 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.
---
## D. MAE
**Points for the task:** 50
**Answer submission format:** entering the answer
**Number of attempts:** 10
**Submission that counts:** the last one
### Statement
There is a sample of $N = 14$ observations (shown in the figure). Each point is given by a pair of coordinates $(x_i, y_i)$.
Consider the linear prediction $\hat{y}(x) = a \cdot x + b$. Find the minimum
$$
MAE = \frac{1}{N} \sum_{i=1}^{N} |\hat{y}(x_i) - y_i|
$$
of this prediction on the sample $(x_i, y_i)$ over all $a, b$.
*Translator's note: the figure above is the copy published with the official editorial; it is the same image as in the original statement. Read from its grid, the 14 points are $(0, 0)$, $(0, 2)$, $(0, 7)$, $(0, 8)$, $(4, 4)$, $(4, 7)$, $(6, 1)$, $(6, 5)$, $(9, 0)$, $(9, 1)$, $(9, 4)$, $(9, 7)$, $(11, 2)$ and $(11, 6)$.*
### Output format
Round the answer to 6 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.
---
## E. The Line Rotates
**Points for the task:** 50
**Answer submission format:** entering the answer
**Number of attempts:** 10
**Submission that counts:** the last one
### Statement
Imagine that we have a rectangle coloured in two colours: part of its area is white and part is black. We need to classify the points inside the rectangle by colour.
We use a very simple classifier: we draw a line $L$ through the centre of the rectangle. Everything that lies on one side of this line is considered black, and everything on the other side is considered white.
Now let us see how well such a line can “guess” the labelling. For any chosen line $L$, one can compute the fraction of the area where the predicted colour coincides with the true one.
*Captions under the figure: left, “True labels”; right, “Predicted labels”.*
Consider the example of a $2 \times 2$ square. It is easy to see that the fraction of correctly predicted area is 0.75.
Among all lines $L$ passing through the centre of the rectangle, what is the largest value that the fraction of correctly predicted area can take? Compute the answers for each of the three pictures below.
*Translator's note: the four figures above are the copies published with the official editorial; they are the same images as in the original statement. In each picture the red dot marks the centre of the rectangle. Cell by cell, the three pictures are as follows (`#` = black, `.` = white, top row first):*
Picture 1 (12 × 5):
```text
####.##.####
#..#.##.#...
####.##.#...
#..#.##.#...
#..#....####
```
Picture 2 (13 × 5):
```text
#...#...#..##
#...#...##.##
#...#...#.#.#
#..##...#...#
###.###.#...#
```
Picture 3 (9 × 5):
```text
###..#...
#.##.#...
#..#.#...
#..#.#...
####.###.
```
### Output format
Write the answers for the three pictures, separated by spaces. Round the answers to 6 decimal places, using a point as the decimal separator.
### Scoring
All three answers match: 50 points.
Two answers match: 25 points.
Test results are **not available** during the tour.
---
## F. NLP
**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.
---
## G. Segments
**Points for the task:** 50
**Answer submission format:** entering the answer
**Number of attempts:** 10
**Submission that counts:** the last one
### Statement
Model training runs of equal duration are scheduled on a shared server. Each run is a time segment. All the endpoints of the segments are distinct. The administrator has configured the queue so that at any moment the server is busy with at most two such runs.
Let $A$ be the number of ways to choose a non-empty set of runs that can be carried out without overlapping in time.
For example:
- if there is one segment on the line, then $A = 1$;
- if there are two intersecting segments, then $A = 2$;
- if there are two non-intersecting segments, then $A = 3$.
Which values from the segment $[1500; 2025]$ can the quantity $A$ take?
### Output format
As your answer, output all suitable values **in ascending order**, separated by spaces.
### Scoring
An exact match of the answer: 50 points.
Test results are **not available** during the tour.
---
## H. Lonely Circle
**Points for the task:** 50
**Answer submission format:** program code
**Number of attempts:** 100
**Submission that counts:** the last one
**Time limit:** 10 seconds
**Memory limit:** 64 MB
**Input:** standard input or input.txt
**Output:** standard output or output.txt
### Statement
Andrey is preparing for an interview for a machine learning internship. To understand the basic ideas of classification, he started with the simplest case: if the points of two classes on the plane can be separated by a line, then the support vector machine (SVM) builds a separating line
$$
w_1 x + w_2 y + b = 0,
$$
and the sign of the expression $w_1 x + w_2 y + b$ determines which class a point belongs to (on one side of the line all points will have the sign $+$, and on the other side, $-$).
This is how Andrey became acquainted with linear classification.
He found a simple code example that shows how to read points from standard input, write them into a table with the columns `x`, `y`, `label`, and train a linear SVM on this data:
```python
import sys
import pandas as pd
from sklearn.svm import SVC
def read_points():
data = []
tokens = sys.stdin.read().split()
it = iter(tokens)
n = int(next(it))
for _ in range(n):
x = float(next(it))
y = float(next(it))
label = int(next(it))
data.append((x, y, label))
df = pd.DataFrame(data, columns=["x", "y", "label"])
return df
df = read_points()
clf = SVC(kernel="linear")
clf.fit(df[["x", "y"]], df["label"])
w1, w2 = clf.coef_[0]
b = clf.intercept_[0]
print(w1, w2, b)
```
At the interview, however, Andrey was given a different task.
Points on the plane with class labels $-1$ and $+1$ are given. It is guaranteed that there exists a circle with centre $(x_0, y_0)$ and radius $R > 0$ such that
- all points of class $-1$ lie strictly inside this circle;
- all points of class $+1$ lie strictly outside this circle.
You need to find **any** such circle $(x_0, y_0, R)$.
Help Andrey solve this problem and pass the interview!
### Input format
The first line contains an integer $n$ ($3 \le n \le 10^5$). Then $n$ lines follow, each with three real numbers $x_i$, $y_i$, $label_i$: the coordinates of the next point and its label.
It is guaranteed that $|x_i|, |y_i| \le 10^9$.
### Output format
Output three real numbers $x$, $y$ and $R$: the coordinates and the radius of the separating circle.
### Scoring
Each test passed gives you 1 point.
The maximum possible score for the task is 50.
Test results are **available** during the tour.
### Example
**Input**
```text
10
0 0 -1
1 1 -1
2 0 -1
-2 0 -1
0 2 -1
4 0 1
-4 0 1
0 4 1
3 4 1
4 3 1
```
**Output**
```text
0 0 3
```
### Notes
This picture corresponds to the first example.
Orange points correspond to $label = -1$, blue points correspond to $label = 1$.
*[Figure: the points of the example (label $-1$ as orange crosses, label $1$ as blue dots) and the circle with centre $(0, 0)$ and radius $3$ on a grid from $-5$ to $5$; see page 12 of the [original statement](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/reg/ai/tasks-ai-9-11-tur1-reg-25-26.pdf).]*