Олимпиада по искусственному интеллекту 9–11 классы — муниципальный этап ВсОШ 2025/2026: задания и ответы

Разбор заданий муниципального этапа ВсОШ 2025/26 по искусственному интеллекту 9-11 классы

Максимальное количество баллов за олимпиаду — 600

Задание 1. Математика в чат-боте Дима выбрал два натуральных числа 𝑎 и 𝑏. Затем он отправил модели ИИ запрос — вычислить 𝑎 𝑏 . Он записал это выражение на бумажке, сфотографировал и загрузил фотографию. Из–за неаккуратного почерка модель распознала выражение как 𝑎 · 𝑏 и посчитала именно его. В итоге её ответ оказался меньше правильного на 110. Какой ответ выдала модель? Ответ: 15 Критерий оценивания: точное совпадение ответа — 100 баллов Максимальный балл за задание — 100 Решение. Из условия мы получаем, что 𝑎 𝑏 − 𝑎𝑏 = 110. Значит, 110 делится на 𝑎. Это оставляет варианты 𝑎 = 1, 2, 5, 10, 11, 22, 55, 110. 𝑎 = 1: 1 − 𝑏 = 110 — нет решений. 𝑎 = 2: 2𝑏−1 − 𝑏 = 55. Левая часть меньше 55 при 𝑏 ≤ 6 и больше 55 при 𝑏 ≥ 7. 𝑎 = 5: 5𝑏−1 − 𝑏 = 22. Левая часть меньше 22 при 𝑏 ≤ 2, равна 22 при 𝑏 = 3, больше 22 при 𝑏 ≥ 4. 𝑎 = 10: 10𝑏−1 − 𝑏 = 11. Левая часть больше 11 при 𝑏 ≥ 3, 𝑏 = 1, 2 не подходят. 𝑎 = 11, 22, 55, 110 разбираются аналогично предыдущему случаю.

Задание 2. Максимальный след по всем перестановкам Матрицей 𝑛 ×𝑚 будем называть таблицу из чисел, состоящую из 𝑛 строк и 𝑚 столбцов. Умножение матриц выполняют по правилу «строка на столбец». Если 𝑝 𝑀= 𝑟

𝑞 , 𝑠

𝑢 𝑁= 𝑤

𝑣 , 𝑥

то 𝑝𝑢 + 𝑞𝑤 𝑀𝑁 = 𝑟𝑢 + 𝑠𝑤

𝑝𝑣 + 𝑞𝑥 . 𝑟𝑣 + 𝑠𝑥

𝑝 Суммой диагональных элементов (следом) матрицы называют число 𝑡𝑟 𝑟 Дана матрица   −1 4 𝐴= . 5 10

𝑞 = 𝑝 + 𝑠. 𝑠

Также даны числа −4, −5, 20, 25. Рассматриваются все 24 матрицы 𝐵 вида 𝑥 𝐵= 𝑧

𝑦 , 𝑤

в которых 𝑥, 𝑦, 𝑧, 𝑤 — некоторая перестановка чисел −4, −5, 20, 25. Для каждой такой 𝐵 рассмотрите произведения 𝐴𝐵 и 𝐵𝐴. а) Hайдите наибольшее возможное значение 𝑡𝑟(𝐴𝐵). Ответ: 339 Критерий оценивания: точное совпадение ответа — 50 баллов б) Hайдите наибольшее возможное значение 𝑡𝑟(𝐵𝐴). Ответ: 339 Критерий оценивания: точное совпадение ответа — 50 баллов Максимальный балл за задание — 100 Решение. Полезное свойство: для любых квадратных матриц одинакового размера tr(𝐴𝐵) = tr(𝐵𝐴). Поэтому достаточно максимизировать tr(𝐴𝐵).   𝑥 𝑦 Пусть 𝐵 = . Тогда 𝑧 𝑤 𝐴𝐵 =

−1

10

!

𝑥 𝑧

− 𝑥 + 4𝑧 𝑦 = 𝑤 5𝑥 + 10𝑧

− 𝑦 + 4𝑤 5𝑦 + 10𝑤

! ,

и потому tr(𝐴𝐵) = (−𝑥 + 4𝑧) + (5𝑦 + 10𝑤) = −𝑥 + 4𝑧 + 5𝑦 + 10𝑤.

Разбор заданий муниципального этапа ВсОШ 2025/26 по искусственному интеллекту 9-11 классы Нужно распределить −5, −4, 20, 25 по 𝑥, 𝑦, 𝑧, 𝑤, чтобы максимизировать линейную форму с коэффициентами −1, 5, 4, 10 соответственно. По неравенству о перестановках максимум достигается, когда наибольшему коэффициенту сопоставлено наибольшее число, и так далее по убыванию: 10 ↔ 25,

5 ↔ 20,

4 ↔ (−4),

(−1) ↔ (−5).

То есть 𝑤 = 25, 𝑦 = 20, 𝑧 = −4, 𝑥 = −5. Тогда tr(𝐴𝐵) = −(−5) + 4 · (−4) + 5 · 20 + 10 · 25 = 5 − 16 + 100 + 250 = 339. Из свойства tr(𝐴𝐵) = tr(𝐵𝐴) такое же значение получается и для 𝐵𝐴. Итак, наибольшая возможная сумма диагональных элементов равна 339.

Задание 3. Минимизация 𝐿1 и 𝐿2 Вы настраиваете простейшую регрессионную модель, которая всегда предсказывает одно и то же число 𝑐 (константная модель). Дан набор истинных значений: 𝑦 = {1, 2, 3, 9, 10, 10}. Рассмотрим две функции качества: 𝐿1 (𝑐) = 𝑖 |𝑦 𝑖 − 𝑐| и 𝐿2 (𝑐) = 𝑖 (𝑦 𝑖 − 𝑐)2 . а) Найдите значение 𝑐1 , минимизирующее 𝐿1 (𝑐). Если оптимальных значений несколько, в ответ запишите наименьшее. Ответ: 3 Критерий оценивания: точное совпадение ответа — 50 баллов б) Найдите значение 𝑐2 , минимизирующее 𝐿2 (𝑐). Если оптимальных значений несколько, в ответ запишите наименьшее. Ответ: 35/6 Критерий оценивания: точное совпадение ответа — 50 баллов Максимальный балл за задание — 100 Решение. Отсортируем значения: 1, 2, 3, 9, 10, 10. a) Минимум 𝐿1 . 𝐿1 (𝑐) минимизируется при медиане выборки. При чётном числе элементов множество оптимумов — это весь отрезок между двумя серединными значениями. Здесь серединные значения 3 и 9, значит оптимумы 𝑐 ∈ [3, 9]. По правилу задачи берём наименьшее: 𝑐 1 = 3.

б) Минимум 𝐿2 . 𝐿2 (𝑐) — квадратичная парабола; минимум достигается в среднем: 𝑐2 =

1 + 2 + 3 + 9 + 10 + 10 35 = . 6 6

(Оптимум единственный, так что указание на «наименьший» здесь ничего не меняет.)

Задание 4. Group By Cистема электронного тестирования фиксирует результаты проверочных работ школьников, которые вы можете скачать в форматах XLSX, ODS или CSV. Файл содержит пять столбцов: • student_id — идентификатор ученика (целое число); • subject — предмет, по которому выполнен тест (строка); • score — полученный балл (вещественное число); • cheat_flag — подозрение на списывание (True/False); • attempt_no — номер попытки (целое число, 1 означает первую попытку). Выполните следующие действия с данными: 1. Очистите столбец score: пустые значения замените на 0, значения меньше 0 также замените на 0, значения больше 100 замените на 100. 2. Удалите строки, где cheat_flag = True. 3. Оставьте только строки, соответствующие первой попытке, то есть те, где attempt_no = 1. 4. Для каждого ученика вычислите его средний балл по предметам — это среднее всех значений score, которые остались после действий выше. 2

Разбор заданий муниципального этапа ВсОШ 2025/26 по искусственному интеллекту 9-11 классы Сколько учеников имеют средний балл в диапазоне 60 ⩽ avg_score < 80? Ответ: 363 Критерий оценивания: точное совпадение ответа — 100 баллов Максимальный балл за задание — 100 Решение. Решение задачи на языке Python: import pandas as pd d f = pd . read_csv ( " t e s t s . c s v " ) df [ " score " ] = df [ " score " ] . f i l l n a (0) mask_neg = d f [ " s c o r e " ] < 0 d f . l o c [ mask_neg , " s c o r e " ] = 0 mask_high = d f [ " s c o r e " ] > 100 d f . l o c [ mask_high , " s c o r e " ] = 100 d f = d f [ d f [ " c h e a t _ f l a g " ] == F a l s e ] d f = d f [ d f [ " attempt_no " ] == 1 ] mean_by_student = d f . groupby ( " s tu de n t _ i d " ) [ " s c o r e " ] . mean ( ) cond = ( mean_by_student >= 6 0 ) & ( mean_by_student < 8 0 ) answer = cond .sum( ) print ( answer )

Задание 5. Дерево непринятия решений Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В машинном обучении часто используют деревья решений. Каждая внутренняя вершина такого дерева соответствует некоторому вопросу, а каждое ребро — выбору ответа (да/нет). Таким образом, за несколько вопросов исходные данные могут быть разбиты на достаточно большое количество классов. Очередным проектом для Димы стало дерево непринятия решений. Его структура похожа на структуру решающего дерева. Это полное бинарное дерево глубины 𝑛. В каждой вершине, кроме вершин последнего уровня, хранится число 𝑝 (0 ⩽ 𝑝 ⩽ 100). Это число обозначает вероятность выбора: с вероятностью 𝑝 процентов алгоритм выберет пойти влево и, соответственно, с вероятностью 100 − 𝑝 процентов — вправо. Договоримся: движение влево обозначим цифрой 0, а движение вправо — цифрой 1. Таким образом, каждая вершина нижнего уровня соответствует двоичной строке длины 𝑛 (последовательности решений от корня до листа). Вероятность получения этой строки равна произведению вероятностей всех выборов, сделанных на пути от корня до листа. Дима уже написал структуру для такого дерева и хочет протестировать её. Для этого он создал дерево глубины 3. Значит, всего в нём 7 внутренних вершин. Каждая вершина имеет своё число 𝑝. Ниже показана схема расположения этих вершин:

Разбор заданий муниципального этапа ВсОШ 2025/26 по искусственному интеллекту 9-11 классы Найдите вероятности всех двоичных строк длины 3 и выведите их в порядке неубывания вероятности. Если вероятности совпадают, строки должны выводиться в лексикографическом порядке.

Формат входных данных В первой строке заданы 7 целых чисел 𝑝 (0 ⩽ 𝑝 ⩽ 100) — вероятности для вершин, как показано на рисунке.

Формат выходных данных Выведите 8 строк. Каждая строка должна содержать двоичную строку длины 3. Строки должны идти в порядке неубывания вероятности. При равенстве вероятностей строки сравниваются лексикографически.

Примеры стандартный ввод 40 90 20 90 100 70 0

стандартный вывод 011 110 001 101 010 100 000 111

Замечание В первом тестовом примере двоичные строки имеют следующие вероятности: • 011 − 0.0 • 110 − 0.0 • 001 − 0.036 • 101 − 0.036 • 010 − 0.04 • 100 − 0.084 • 000 − 0.324 • 111 − 0.48

Решение В задаче нужно посчитать вероятность для каждого листа. Так как каждая такая вероятность является произведением трёх чисел (вероятностей выбора в вершинах), для сравнения достаточно сравнивать произведения этих чисел, умноженных на 100 (то есть вероятности в процентах). Давайте явно выпишем все 8 таких произведений и для каждого запомним соответствующую строку из трёх бит. После этого отсортируем пары (вероятность, строка) по вероятности и выведем строки в получившемся порядке. Это и будет ответом. #include <i o s t r e a m > #include <v e c t o r > #include <a l g o r i t h m > using namespace s t d ; int main ( ) { i o s : : sync_with_stdio ( f a l s e ) ; cin . t i e ( nullptr ) ; int p1 , p2 , p3 , p4 , p5 , p6 , p7 ; c i n >> p1 >> p2 >> p3 >> p4 >> p5 >> p6 >> p7 ; int int int int int

p000 = p1 ∗ p2 ∗ p4 ; p001 = p1 ∗ p2 ∗ ( 1 0 0 − p4 ) ; p010 = p1 ∗ ( 1 0 0 − p2 ) ∗ p5 ; p011 = p1 ∗ ( 1 0 0 − p2 ) ∗ ( 1 0 0 − p5 ) ; p100 = ( 1 0 0 − p1 ) ∗ p3 ∗ p6 ; 4

Разбор заданий муниципального этапа ВсОШ 2025/26 по искусственному интеллекту 9-11 классы int p101 = ( 1 0 0 − p1 ) ∗ p3 ∗ ( 1 0 0 − p6 ) ; int p110 = ( 1 0 0 − p1 ) ∗ ( 1 0 0 − p3 ) ∗ p7 ; int p111 = ( 1 0 0 − p1 ) ∗ ( 1 0 0 − p3 ) ∗ ( 1 0 0 − p7 ) ; v e c t o r <p a i r <int , s t r i n g >> v = { { p000 , " 000 " } , { p001 , " 001 " } , { p010 , " 010 " } , { p011 , " 011 " } , { p100 , " 100 " } , { p101 , " 101 " } , { p110 , " 110 " } , { p111 , " 111 "} }; s o r t ( v . b e g i n ( ) , v . end ( ) ) ; for ( auto &[p , s ] : v ) { c o u t << s << ’ \n ’ ; } return 0 ; } Максимальный балл за задание — 100

Задание 6. Тепловая карта Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Слава готовит постер на конференцию. К сожалению, сейчас его тепловая карта не влезает на постер: она слишком большая. Поэтому Слава решил выделить на текущей карте некоторый прямоугольный фрагмент и использовать его для презентации. Славина тепловая карта выглядит как таблица из 𝑛 строк и 𝑚 столбцов. Клетка на пересечении 𝑖-й строки и 𝑗-го столбца имеет цвет 𝑐 𝑖𝑗 . Используются 𝑘 цветов, которые пронумерованы от 1 до 𝑘. Пример аналогичной карты приведён справа. Слава хочет продемонстрировать весь размах значений, поэтому на выбранном фрагменте должна быть хотя бы одна клетка каждого цвета. При этом юный докладчик хочет минимизировать площадь карты, ведь ему нужно уместить её на постер. Помогите ему: найдите прямоугольник, который можно будет вырезать из его карты так, чтобы на нём были клетки всех 𝑘 цветов. Гарантируется, что на исходной тепловой карте присутствуют клетки всех 𝑘 цветов.

Формат входных данных В первой строке вводятся три натуральных числа 𝑛, 𝑚, 𝑘 (1 ⩽ 𝑛, 𝑚 ⩽ 250, 1 ⩽ 𝑘 ⩽ 20). В следующих 𝑛 строках задаётся по 𝑚 натуральных чисел 𝑐 𝑖𝑗 (1 ⩽ 𝑐 𝑖𝑗 ⩽ 𝑘).

Формат выходных данных Выведите 4 числа 𝑥 1 , 𝑦1 , 𝑥2 , 𝑦2 , задающие прямоугольник, который нужно вырезать. Прямоугольник задаётся своими верхней и нижней строками (𝑥1 ,𝑥2 ) и левым и правым столбцами (𝑦1 ,𝑦2 ). Если есть несколько способов вырезать график наименьшей площади, выведите любой.

Примеры стандартный ввод 343 1122 3113 1222

стандартный вывод 1324

Разбор заданий муниципального этапа ВсОШ 2025/26 по искусственному интеллекту 9-11 классы

Замечание

Все возможные варианты вырезать график наименьшей площади для первого примера.

Решение Необходимо найти прямоугольную подматрицу минимальной площади, содержащую все 𝑘 цветов. Зафиксируем верхнюю и нижнюю строки 𝑙 и 𝑟 (1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛). Тогда задача сводится к поиску минимального по ширине диапазона столбцов, который вместе со строками [𝑙..𝑟] покрывает все цвета. Для удобства предварительно посчитаем 2D-префиксные суммы для каждого цвета 𝑐: pref[𝑐][𝑖][𝑗] — сколько клеток цвета 𝑐 находится в прямоугольнике [1..𝑖] × [1..𝑗]. Тогда количество клеток цвета 𝑐 в прямоугольнике строк [𝑙..𝑟] и столбцов [𝑥..𝑦] можно получить за 𝑂(1): cnt = pref[𝑐][𝑟][𝑦]−pref[𝑐][𝑙−1][𝑦]−pref[𝑐][𝑟][𝑥−1]+pref[𝑐][𝑙−1][𝑥−1]. Далее перебираем все пары строк (𝑙,𝑟) и применяем по столбцам двухуказательный проход. Левый указатель 𝑥 фиксируем, а правый 𝑦 двигаем вправо, пока прямоугольник [𝑙..𝑟] × [𝑥..𝑦] не начнёт содержать все цвета. Как только это произойдёт, можно будет обновить ответ площадью (𝑟 − 𝑙 + 1)(𝑦 − 𝑥 + 1), а затем сдвинуть 𝑥 дальше. Так как указатель 𝑦 для фиксированных (𝑙, 𝑟) только растёт, проход по столбцам работает за 𝑂(𝑚). Итого: префиксы считаются за 𝑂(𝑘𝑛𝑚), перебор пар строк даёт 𝑂(𝑛 2 ) запусков двух указателей, каждый за 𝑂(𝑚 · 𝑘) на проверку наличия всех цветов (в данной реализации проверка идёт перебором всех 𝑘 цветов через префиксы). Общая сложность данной версии: 𝑂(𝑘𝑛𝑚 + 𝑛 2 𝑚 𝑘). #include <i o s t r e a m > #include <v e c t o r > #include <a l g o r i t h m > using namespace s t d ; int main ( ) { i o s : : sync_with_stdio ( f a l s e ) ; cin . t i e ( nullptr ) ; int n , m, k ; c i n >> n >> m >> k ; v e c t o r <v e c t o r <int>> v ( n , v e c t o r <int >(m) ) ; for ( int i = 0 ; i < n ; ++i ) { f o r ( int j = 0 ; j < m; ++j ) { c i n >> v [ i ] [ j ] ; −−v [ i ] [ j ] ; } } v e c t o r <v e c t o r <v e c t o r <int>>> p r e f ( k , v e c t o r <v e c t o r <int >>(n + 1 , v e c t o r <int >(m + 1 , 0 ) ) ); for ( int c = 0 ; c < k ; ++c ) { f o r ( int i = 1 ; i <= n ; ++i ) { 6

Разбор заданий муниципального этапа ВсОШ 2025/26 по искусственному интеллекту 9-11 классы f o r ( int j = 1 ; j <= m; ++j ) { pref [ c ] [ i ] [ j ] = pref [ c ] [ i − 1 ] [ j ] + pref [ c ] [ i ] [ j − 1] − pref [ c ] [ i − 1 ] [ j − 1] + ( v [ i − 1 ] [ j − 1 ] == c ) ; } } } int min_area = n ∗ m; v e c t o r <int> ans ( 4 , −1); for ( int l = 0 ; l < n ; ++l ) { f o r ( int r = l ; r < n ; ++r ) { int y = 0 ; f o r ( int x = 0 ; x < m; ++x ) { if (x > y) y = x ; while ( y < m) { bool ok = true ; for ( int c = 0 ; c < k ; ++c ) { int c n t = p r e f [ c ] [ r + 1 ] [ y + 1 ] − pref [ c ] [ l ] [ y + 1] − pref [ c ] [ r + 1 ] [ x ] + pref [ c ] [ l ] [ x ] ; i f ( c n t == 0 ) { ok = f a l s e ; break ; } } i f ( ok ) break ; ++y ; } i f ( y == m) { x = y; continue ; } int a r e a = ( r − l + 1 ) ∗ ( y − x + 1 ) ; i f ( a r e a < min_area ) { min_area = a r e a ; ans = { l + 1 , x + 1 , r + 1 , y + 1 } ; } } } } c o u t << ans [ 0 ] << ’ ␣ ’ << ans [ 1 ] << ’ ␣ ’ << ans [ 2 ] << ’ ␣ ’ << ans [ 3 ] << ’ \n ’ ; return 0 ; } Максимальный балл за задание — 100