Автор Заключительный этап 2026 всероссийской олимпиады школьников по программированию информатика задания, ответы и решения для 9, 10, 11 класса. Данная олимпиада прошла у школьников 22-28 марта в Москве.
→ Задания: скачать
→ Решение: скачать
Необходимо считывать данные из стандартного потока ввода. Выходные данные необходимо выводить в стандартный поток вывода. Баллы за подзадачу начисляются только если все тесты этой и необходимых подзадач пройдены. Решение запускается на тестах для определенной подзадачи, если все тесты всех необходимых подзадач пройдены.
Олимпиада по программированию 9, 10, 11 класс заключительный этап 2026
inf-prog-final-vos-2026-zadanieЗадача 1. Распределённые системы
Ограничение по времени: 1 секунда Ограничение по памяти: 1024 мегабайта В компании n серверов, пронумерованных числами от 1 до n. На i-м сервере запущены ai сервисов. Иногда серверы могут отключаться, поэтому для каждого сервера был определён резервный сервер. Для сервера с номером i резервным является сервер с номером pi . Если у i-го сервера pi = i, то это сервер повышенной надёжности, и он никогда не отключается. Для любых двух различных серверов i и j номера их резервных серверов pi и pj не совпадают.
Таким образом, p — это перестановка длины n, то есть каждое число от 1 до n встречается ровно один раз среди значений p1, . . . , pn. Процесс отключения сервера происходит следующим образом. Если сервер i отключается, то все запущенные на нём сервисы перемещаются на сервер с номером pi , а сервер i заменяется на новый сервер, на котором не запущены никакие сервисы. Номер этого сервера и номер его резервного сервера остаются без изменений. Перенос сервисов и замена сервера очень быстрый процесс, во время него не может произойти новых отключений.
В компании планируется провести тестирование работоспособности системы. Для этого будут отключены не более k серверов. Отключения проводятся последовательно, то есть никакие два сервера не отключаются одновременно. Определите максимальное число сервисов, которые могут оказаться на одном сервере после отключения не более k серверов.
Задача 2. Расследование в Темерии
Темерия — одно из самых могущественных королевств Севера со столицей в городе Вызима. Чародейка Трисс, которая живет в городе Вызима, обнаружила сильные магические аномалии и решила исследовать королевство Темерия, чтобы найти их источник. В Темерии располагаются n городов, пронумерованных числами от 1 до n, столица Вызима имеет номер 1. Города соединены n − 1 двусторонними дорогами, i-я дорога соединяет города с номерами ui и vi и имеет длину wi . Гарантируется, что Трисс может добраться из любого города в любой другой, пользуясь только этими дорогами. Трисс планирует начать и закончить свой путь в Вызиме, побывав во всех n городах. Трисс может ходить по дорогам, но это медленно.
У неё есть k кристаллов телепортации, которыми она может воспользоваться для мгновенного перемещения между городами. В любой момент Трисс может оставить кристалл в городе, где она находится. В дальнейшем чародейка может воспользоваться ранее оставленным кристаллом и мгновенно вернуться по кратчайшему пути в город, в котором она ранее оставила кристалл. После использования кристалл разрушается. Трисс может оставлять и использовать кристаллы в произвольном порядке. К сожалению, телепортация не проходит бесследно. А именно, если Трисс, находясь в городе a, воспользовалась кристаллом и попала в город b, то во всех городах, лежащих на кратчайшем пути от a до b, включая a и b, остается магический след и в дальнейшем через такие города другой маршрут телепортации проходить не может. Помогите Трисс. Для каждого j от 1 до k включительно, определите, какое минимальное расстояние надо пройти чародейке, чтобы обойти все города королевства и вернуться в Вызиму, потратив при этом не более чем j кристаллов.
Задача 3. Скобки и деревья
Это интерактивная задача с двойным запуском. В этой задаче рассматриваются корневые деревья без порядка на детях. Корневое дерево без порядка на детях состоит из корня, у которого может быть ноль или более детей. Каждый ребенок в свою очередь является корневым деревом без порядка на детях. При этом, как и следует из названия дерева, порядок, в котором перечисляются дети, не важен, то есть деревья, изображенные на рисунке ниже являются одним и тем же деревом без порядка на детях. Далее будем называть корневые деревья без порядка на детях просто деревьями. Любое дерево можно закодировать в виде правильной скобочной последовательности (далее — ПСП) следующим образом: Дерево, состоящее из одной вершины, кодируется как «()».
Пусть после удаления корня дерево распадается на поддеревья t1, t2, . . . , tk, где k — количество детей корня исходного дерева. Положим, что s1, . . . , sk — строки, которые кодируют деревья t1, . . . , tk. Тогда для любой перестановки a = [a1, a2, …, ak] чисел от 1 до k исходное дерево может быть закодировано ПСП «(sa1 sa2 . . . sak )». Обратите внимание, что одно и то же дерево может быть закодировано различными ПСП. Например, дерево, изображенное на рисунке ниже, может быть закодировано с помощью ПСП «(()(()))» или «((())())». Вам требуется научиться кодировать произвольную последовательность деревьев u1, . . . , un в виде одного корневого дерева w. Чтобы проверить, что ваш способ кодирования корректный, ваше решение будет запущено два раза.
Задача 4. Спортивная тренировка
Несколько школьников занимаются в спортивной секции. В начале тренировки в зале присутствуют n человек, а затем в течение занятия к ним по одному присоединяются еще q человек. Рост всех n + q школьников различен, пронумеруем школьников от 1 до n + q по возрастанию роста. На тренировке школьники выполняют упражнения с мячом. Школьники выстраиваются в ряд слева направо в некотором порядке. В зависимости от порядка, в котором они выстроились, некоторые пары школьников образуют допустимые пары. Пара школьников, стоящих на позициях i и j, где i < j, образует допустимую пару, если выполнено одно из двух условий: • школьник на i-й позиции является самым левым школьником из тех, которые ниже школьника на j-й позиции и стоят левее него; • школьник на j-й позиции является самым правым школьником из тех, которые ниже школьника на i-й позиции и стоят правее него.
Например, если в ряд стоят школьники с номерами [6, 7, 3, 5, 1, 2], то допустимыми являются пары школьников с номерами (6, 2), (6, 7), (7, 2), (3, 2), (3, 5), (5, 2), (1, 2). У упражнения есть два уровня сложности, на каждом из которых есть свои допустимые броски. При выполнении упражнения на любом уровне сложности запрещается бросать мяч школьнику, у которого он уже был во время выполнения этого упражнения. На первом уровне сложности школьник может бросить мяч любому школьнику, с которым он образует допустимую пару и который ниже его. Например, если в ряд стоят школьники с номерами [6, 7, 3, 5, 1, 2], то школьник с номером 3 может бросить мяч только школьнику с номером 2, школьник с номером 5 — школьникам с номерами 3 и 2, школьник с номером 1 не может бросить мяч никому. На втором уровне сложности школьник может бросить мяч любому школьнику, с которым он образует допустимую пару.
Например, если в ряд стоят школьники с номерами [6, 7, 3, 5, 1, 2], то школьник с номером 3 может бросить мяч школьникам с номерами 2 и 5, школьник с номером 5 — школьникам с номерами 3 и 2, школьник с номером 1 может бросить мяч школьнику с номером 2. Упражнение выполняется следующим образом. Тренер выбирает уровень сложности упражнения t. Один из школьников берёт мяч и совершает допустимый бросок. Школьник, получивший мяч, снова совершает допустимый бросок, и т.д. Броски выполняются, пока это возможно. Если допустимых бросков несколько, можно выбрать любой из них, но запрещается бросать мяч тому из школьников, у кого уже был мяч во время выполнения этого упражнения.
Участники, находящиеся на тренировке, выполняют допустимые для этого уровня сложности броски таким образом, чтобы было произведено максимальное число бросков. Затем q раз к тренирующимся присоединяется еще один школьник. Он встаёт справа или слева от уже выполнявших упражнение. После этого упражнение выполняется заново на том же уровне сложности. Для начального состава участников тренировки и после добавления каждого нового школьника необходимо определить, какое максимальное количество бросков смогут сделать участники тренировки.
Задача 5. Обобщённые шахматы
Михаил решил научиться играть в обобщённые шахматы, для чего подготовил шахматную доску размером n × n клеток. Клетку на пересечении i-й строки и j-го столбца он раскрасил в цвет aij . Михаил начинающий игрок и мог раскрасить доску неправильно. Поэтому некоторые клетки доски, возможно, потребуется перекрасить в другой цвет. Доска считается раскрашенной правильно при выполнении двух условий: • клетки доски покрашены в не более чем два различных цвета; на доске нет соседних по стороне клеток, раскрашенных в один и тот же цвет. Михаил задумался о том, что играть на большой доске ему будет слишком сложно. Поэтому он, возможно, выпилит из своей доски доску поменьше, оставив участок, состоящий из первых r строк и первых c столбцов, и раскрасит правильно только этот участок. Для каждой пары чисел r и c (1 ⩽ r ⩽ n, 1 ⩽ c ⩽ n) вычислите значение brc — минимальное количество клеток, которые надо перекрасить Михаилу так, чтобы прямоугольный участок доски из первых r строк и первых c столбцов был раскрашен правильно.
Задача 6. Ночь, улица, фонарь, аптека
Вдоль длинной улицы стоят фонарные столбы, на которых расположены n фонарей. Введём систему координат вдоль улицы. Столб, на котором размещён i-й фонарь, находится в точке с координатой xi . В первых шести подзадачах данной задачи, оценивающихся в 85 баллов, никакие два фонаря не прикреплены к одному и тому же столбу, то есть все значения xi различны. В последних двух подзадачах на каждом столбе может быть не более двух фонарей. Для освещения улицы можно включить некоторые фонари. Включённый фонарь с номером i имеет яркость si . Он светит таким образом, что освещает непрерывный участок улицы длиной si метров от столба, на котором он находится. Каждый включённый фонарь можно повернуть либо налево, либо направо.
Если направить i-й фонарь налево, он освещает отрезок улицы [xi − si , xi ], а если направо, то [xi , xi + si ]. Выберем непустое множество фонарей, которые будут включены для освещения участка улицы. Будем называть это множество фонарей экономным, если можно направить каждый выбранный фонарь налево или направо таким образом, чтобы выполнялись два условия: • освещённые отрезки формируют непрерывный отрезок улицы; • никакой отрезок ненулевой длины не освещён двумя или более фонарями одновременно. На рисунке ниже показаны экономные подмножества из двух фонарей для второго примера из условия и способы осветить непрерывный участок улицы. Над каждым фонарем написана его яркость.
Задача 7. Марсианский рюкзак
Марсианин Марвин собирает рюкзак. Перед ним лежат n предметов, пронумерованных числами от 1 до n. Каждый предмет имеет две характеристики: i-й предмет обладает странностью wi и стоимостью ci . Странность предмета является неотрицательным целым числом, двоичная запись которого содержит не более k бит (0 ⩽ wi < 2 k ), стоимость предмета является неотрицательным целым числом, не превышающим 109 (0 ⩽ ci ⩽ 109 ). Общая стоимость набора предметов равна сумме стоимостей входящих в него предметов, а общая странность этого набора определяется как побитовая операция «ИЛИ» странностей входящих в него предметов.
Марвин называет набор предметов ценным, если его общая стоимость не меньше C. Для всех i от 1 до n Марвин хочет выбрать из предметов с номерами, не превосходящими i, ценный набор предметов такой, чтобы его общая странность была как можно меньше. Побитовое «ИЛИ» набора целых чисел определяется следующим образом: рассмотрим двоичные записи этих чисел. Тогда i-й бит результата равен 1, если хотя бы у одного из чисел набора i-й бит равен 1. В языках программирования эта операция обозначается знаком «|». Например, (10 | 3 | 9) = (10102 | 00112 | 10012) = 10112 = 11.
Смотрите на сайте олимпиады
Региональный этап 2026 олимпиада по программированию 9, 10, 11 класса задания и ответы