Информатика (с ответами). Всероссийская олимпиада школьников в Москве (2024-2025 год)

Всероссийская олимпиада школьников по информатике 2024-2025

Региональный этап, день 2, 20 января 2025 года

Задача 7. Главное правило личных олимпиад

Ограничение по времени:

1 секунда

Ограничение по памяти:

512 мегабайт

Напомним главное правило написания личных олимпиад: по каждой задаче нужно набрать бал-

лы! Нельзя уйти с контеста с нулем по задаче.

Промоделируем тур олимпиады. Пусть на туре предложено n задач, i-я задача состоит из k_i

подзадач, j-я подзадача i-й задачи приносит c_i,jбаллов. Зависимостей между подзадачами нет,

поэтому можно в каждой задаче выбрать любое множество подзадач и его решить. При этом нель-

зя выбрать пустое множество, ведь тогда по задаче будет 0 баллов, а это противоречит главному

правилу написания личных олимпиад.

Проверьте, можно ли, придерживаясь главного правила личных олимпиад, набрать на туре ровно

s баллов.

Формат входных данных

Первая строка содержит два целых числа n, s (1 ::: n ::: 100 000, 1 ::: s ::: 100 000) количество

задач в контесте и необходимую сумму баллов, соответственно. Далее следуют описания задач.

Описание каждой задачи состоит из двух строк.

Первая строка описания i-й задачи содержит одно целое число k_i(1 ::: k_i::: 100 000) количество

подзадач в i-й задаче.

Вторая строка описания i-й задачи содержит k_iцелых чисел ci,1, ci,2, . . . , ci,ki (1 ::: c_i,j::: 100 000)

баллы за подзадачи.

Гарантируется, что сумма k₁+ k₂+ . . . + k_nпо всем задачам не превосходит 100 000.

Гарантируется, что произведение (k₁+ k₂+ . . . + k_n) · s не превосходит 10⁷.

Формат выходных данных

Если решения не существует, выведите «No».

В противном случае в первой строке выведите «Yes». Далее необходимо вывести описание ре-

шенных подзадач для каждой задачи.

Описание i-й задачи начинается с целого числа m_i(1 ::: m_i::: k_i) количества решенных

подзадач i-й задачи. Далее следуют m_iразличных целых чисел pi,1, pi,2, . . . , pi,mi (1 ::: p_i,j::: k_i)

номера решенных подзадач в i-й задаче.

Если существует несколько подходящих способов набрать s баллов, выведите любое из них.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи

и необходимых подзадач успешно пройдены

Дополнительные

Необходимые

Информация о

Подзадача

Баллы

ограничения

подзадачи

проверке

n = 1

первая ошибка

n = 2

первая ошибка

k₁+ k₂+ . . . + k_n::: 20

первая ошибка

k_i= 1

первая ошибка

n · s ::: 100 000, s ::: 1 000

первая ошибка

1 - 5

первая ошибка

Страница 3 из 6

Всероссийская олимпиада школьников по информатике 2024-2025

Региональный этап, день 2, 20 января 2025 года

Задача 8. Туристический маршрут

Ограничение по времени:

1 секунда

Ограничение по памяти:

512 мегабайт

Школьники приехали на экскурсию в новый город и решили осмотреть его достопримечатель-

ности. Представим город в виде прямоугольной сетки n × m, в некоторых клетках которой могут

находиться достопримечательности.

Друзья начинают свой путь в клетке (1, 1), они хотят дойти до клетки (n, m), а затем вернуться

обратно. В городе есть k достопримечательностей, они расположены в клетках (x₁, y₁), . . . , (x_k, y_k),

друзья обязательно хотят посетить их все.

За одну минуту можно перейти из клетки (a, b) в клетку (c, d), если они являются соседними по

стороне, то есть выполняется равенство |a-c|+|b-d| = 1. Легко видеть, что на маршрут необходимо

потратить хотя бы 2n + 2m - 4 минут, будем рассматривать только такие маршруты.

Будем называть маршрут интересным, если выполняются следующие условия:

• для того, чтобы пройти маршрут, друзья потратят ровно 2n + 2m - 4 минут;

• маршрут проходит через каждую клетку не более одного раза.

• маршрут проходит через все клетки, которые содержат достопримечательности.

Помогите школьникам понять, сколько существует различных интересных маршрутов. Так как

это число может оказаться достаточно большим, то выведите его остаток при делении на 10⁹+ 7.

Формат входных данных

В первой строке указаны числа n, m и k (3 ::: n, m ::: 10⁶, 0 ::: k ::: 2 000).

В последующих k строках указано по паре чисел x_i, y_i(1 ::: x_i::: n, 1 ::: y_i::: m), гарантируется,

что все пары (x_i, y_i) различны. То есть для любой пары индексов (i, j) (1 ::: i < j ::: k) верно хотя

бы одно из двух: x_i/= x_jили y_i/= y_j.

Формат выходных данных

Выведите единственное число остаток от деления числа интересных маршрутов на 10⁹+ 7.

Страница 5 из 6

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Общая информация по задачам первого тура

Задача

Тип задачи

Ограничения

1. Лестница для участников олимпиады

стандартная

0.5 с, 1024 МБ

2. Пересменка в Сириусе

стандартная

1 с, 1024 МБ

3. Сочи Парк

стандартная

1 с, 1024 МБ

4. Лягушки на дереве

стандартная

2 с, 1024 МБ

Необходимо считывать данные из стандартного потока ввода. Выходные данные необходимо

выводить в стандартный поток вывода.

Баллы за подзадачу начисляются только если все тесты этой и необходимых подзадач пройде-

ны. Решение запускается на тестах для определенной подзадачи, если все тесты всех необходимых

подзадач пройдены. В одной из задач можно получить частичные баллы за подзадачу. Для тестиро-

вания подзадачи достаточно, чтобы во всех необходимых подзадачах был получен положительный

балл.

Во всех подзадачах каждой задачи во время тура вам показываются баллы за подзадачу, если

все тесты пройдены, либо первая ошибка и номер теста.

Для некоторых подзадач может также требоваться, чтобы были пройдены все тесты из условия.

Для таких подзадач указана дополнительно буква У.

Страница 1 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Задача 1. Лестница для участников олимпиады

Ограничение по времени:

0.5 секунд

Ограничение по памяти:

1024 мегабайта

В ОЦ «Сириус» любимым местом для сбора и неформального общения

школьников служат различные лестницы. Но количество участников олимпи-

ады по информатике значительно превосходит количество участников любой

образовательной программы, и подходящей для них лестницы среди имеющих-

ся не нашлось, поэтому служба оснащения решила построить новую лестницу,

используя специальную заготовку.

Заготовка представляет собой таблицу из h строк и w столбцов, прону-

мерованных сверху вниз и слева направо соответственно. В каждой клетке

таблицы записано одно число - ноль или единица. Лестницу можно сделать

только из тех клеток таблицы, в которых записана единица.

Полученная лестница образуется из множества клеток, в которых записа-

на единица, находящихся в нескольких последовательных строках таблицы. Множество выбранных

клеток в каждой строке лестницы должно быть непрерывным отрезком. При этом в каждой следу-

ющей строке, входящей в лестницу, должно быть выбрано не меньше клеток, чем в предыдущей,

находящейся непосредственно над нею, строке, а самые левые выбранные клетки в каждой строке

должны располагаться в одном и том же столбце.

Ниже приведен пример лестницы.

Найдите в заданной таблице максимальное количество клеток, образующих лестницу.

Формат входных данных

Первая строка входных данных содержит два целых числа h и w

(1 ⩽ h, w ⩽ 2 · 10⁵, h · w ⩽ 4 · 10⁶) - количество строк и столбцов табли-

цы соответственно.

Каждая из следующих h строк содержит по w символов, каждый из кото-

рых равен 0 или 1 - числа, написанные в клетках таблицы.

Формат выходных данных

Выведите одно число - максимальное количество клеток, образующих

лестницу.

Система оценивания

Ограничения

Необходимые

Подзадача

Баллы

подзадачи

h, w

h, w ⩽ 50

h, w ⩽ 400

У, 1

h · w ⩽ 200 000

У, 1, 2

У, 1-3

Страница 2 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Задача 2. Пересменка в Сириусе

Ограничение по времени:

1 секунда

Ограничение по памяти:

1024 мегабайта

Участники образовательных программ иногда задумываются, почему между двумя программа-

ми обычно бывает перерыв в несколько дней. Ответ прост: сотрудникам Сириуса необходимо после

очередной программы привести в порядок жилые номера.

На одном этаже в гостинице ОЦ «Сириус» находятся n номе-

ров, пронумерованных от 1 до n. После проведения образователь-

ной программы все эти номера нуждаются в ремонте.

К ремонтным работам привлечены k сотрудников, пронумеро-

ванных от 1 до k. За i-м сотрудником закреплён диапазон номеров

с l_iпо r_iвключительно, а также зафиксирован номер m_iиз это-

го диапазона, с которого он должен начать обход своих номеров.

Диапазоны номеров у разных сотрудников могут пересекаться и

даже совпадать.

Сотрудники в некотором порядке направляются с базы для вы-

полнения работ. Следующий сотрудник направляется только после

возвращения предыдущего на базу.

Когда i-го сотрудника направляют на выполнение работ, он

сначала идёт в номер m_i. Если этот номер всё ещё нуждается в

ремонте, то сотрудник ремонтирует его, а также посещает все но-

мера из диапазона с l_iпо r_i, за который он отвечает, и ремонтирует

все нуждающиеся в ремонте номера из этого диапазона, после чего возвращается на базу. После это-

го все номера из диапазона с l_iпо r_iболее не нуждаются в ремонте.

Если же первый посещённый сотрудником номер m_iне нуждается в ремонте, поскольку его уже

отремонтировали ранее направленные для выполнения работ коллеги, то сотрудник сразу возвраща-

ется на базу, надеясь, что коллеги уже отремонтировали и все остальные номера из его диапазона.

В этом случае некоторые другие номера из диапазона с l_iпо r_iвсё еще могут нуждаться в ремонте.

Определите, можно ли при подобном подходе сотрудников к выполнению своих обязанностей

направить их всех для выполнения работ в таком порядке, чтобы в итоге все номера от 1 до n

оказались отремонтированы.

Формат входных данных

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно

целое число t (1 ⩽ t ⩽ 10⁵) - количество наборов входных данных. Далее следует описание наборов

входных данных.

Первая строка каждого набора входных данных содержит два целых числа n и k

(1 ⩽ n, k ⩽ 5 · 10⁵) - количество номеров и количество сотрудников соответственно.

В каждой из последующих k строк содержится три целых числа l_i, m_iи r_i

⩽ l_i⩽ m_i⩽ r_i⩽ n) - первый номер диапазона ответственности i-го сотрудника, номер

из диапазона, с которого он должен начать обход своих, и последний номер из его диапазона,

соответственно.

Гарантируется, что сумма n и k по всем наборам входных данных не превосходит 5 · 10⁵.

Формат выходных данных

Для каждого набора входных данных в отдельной строке выведите «YES», если можно отремон-

тировать все номера, и «NO» - в противном случае.

Страница 4 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Система оценивания

Обозначим за N сумму n по всем наборам входных данных, за K - сумму k по всем наборам

входных данных.

Дополнительные ограничения

Необх.

Подзадача

Баллы

подзадачи

n, N

k, K

дополнительно

K ⩽ 10 000

m_i= l_i

N ⩽ 500

k ⩽ 8

n ⩽ 18

K ⩽ 500

n ⩽ 50

K ⩽ 50

n ⩽ 150

K ⩽ 150

У, 4

N ⩽ 500

K ⩽ 500

За каждым сотрудником

K ⩽ 10 000

закреплен номер 1 или номер n

Для каждого сотрудника

K ⩽ 10 000

найдется номер, который

закреплён только за ним

Для каждого сотрудника

найдется номер, который

закреплён только за ним

K ⩽ 10 000

r_i- l_i= r_j- l_jдля любых i, j

K ⩽ 10 000

Любое m_iсовпадает с l_iили r_i

n ⩽ 10 000

K ⩽ 10 000

У, 2-6

K ⩽ 10 000

У, 1-8, 10-12

У, 1-13

Пример

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

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

YES

5 2

3 4 5

1 3 3

5 3

1 2 4

2 4 5

3 3 3

Замечание

В первом наборе входных данных из примера нужно сначала направить для выполнения ре-

монтных работ второго сотрудника, он отремонтирует номера с первого по третий. Затем первый

сотрудник направится в номер 4. Так как он еще нуждается в ремонте, первый сотрудник отремон-

тирует оставшиеся номера в своем диапазоне. В результате все номера будут отремонтированы.

Во втором наборе данных выбрать подходящий порядок отправки сотрудников невозможно.

Страница 5 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Задача 3. Сочи Парк

Ограничение по времени:

1 секунда

Ограничение по памяти:

1024 мегабайта

В Сочи Парке открылся новый аттракцион. Вдоль прямой расположены n целей, координата

i-й цели равна x_i(1 ⩽ i ⩽ n). Посетители должны поразить все эти цели в произвольном порядке.

Для поражения целей используются мячики. Если посетитель находится в точке с координатой x и

хочет поразить цель, находящуюся в точке x_i, ему потребуется потратить (x - x_i)²калорий.

Посетитель входит в аттракцион в точке с координатой x₀. Неограниченные запасы мячиков

находятся в точке входа, а также во всех точках на расстоянии d друг от друга, то есть в точках

x₀+ kd, где k - произвольное целое число. Переносить мячики запрещено правилами аттракциона,

поэтому бросать их можно только из этих точек.

В день между турами m участников олимпиады посетят Сочи Парк. Участники соревнования

находятся в разной физической форме, поэтому j-му участнику олимпиады для перемещения на

расстояние d требуется t_jкалорий.

Вам нужно определить, какое минимальное число калорий необходимо каждому участнику для

поражения всех целей аттракциона.

Формат входных данных

В первой строке задано одно целое число n (1 ⩽ n ⩽ 3 · 10⁵) - количество целей в аттракционе.

Во второй строке заданы n целых чисел x₁, x₂, . . . , x_n(0 ⩽ x_i⩽ 10⁹) - координаты целей.

В третьей строке заданы два целых числа x₀и d (0 ⩽ x₀⩽ 10⁹, 1 ⩽ d ⩽ 2 · 10⁶) - точка входа

посетителя аттракциона и расстояние между местами нахождения запасов мячиков.

В четвертой строке задано одно целое число m (1 ⩽ m ⩽ 6 · 10⁵) - количество участников

олимпиады.

В следующих m строках содержится по одному целому числу t_j(0 ⩽ t_j⩽ 10⁸) - количество

энергии, необходимое j-му участнику олимпиады для перемещения между двумя соседними местами

нахождения запасов мячиков.

Формат выходных данных

Для каждого участника олимпиады выведите одно целое число - минимальное количество,

необходимое ему для перемещения и поражения всех целей.

При данных ограничениях ответ не превосходит максимального значения 64-битного знакового

типа данных. Однако для промежуточных вычислений может понадобиться тип данных int128

в C++ (поддерживается только в компиляторе GNU C++), BigInteger в Java, int в Python.

Страница 6 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Примеры

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

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

4 0 7

2 3

30 239 57 179

355

0 7

525

3378

93311

100

100000

49597

100 2 101 666

9 10

159

1043

777

703

Замечание

В первом тесте для второго участника (t₂= 1) оптимальным будет следующий алгоритм пора-

жения целей:

1. Переместиться из точки x₀= 2 в точку x₀- d = -1, потратив t₂= 1 калорию. Обратите

внимание, координата посетителя может быть отрицательной.

2. Поразить цель в точке x₂= 0, потратив (-1 - 0)²= 1 калорию.

3. Переместиться в точку -1 + 2d = 5, потратив 2t₂= 2 калории.

4. Поразить цель в точке x₁= 4, потратив (5 - 4)²= 1 калорию.

5. Переместиться в точку 5 + d = 8, потратив t₂= 1 калорию.

6. Поразить цель в точке x₃= 7, потратив (8 - 7)²= 1 калорию.

Суммарные затраты энергии равны 1 + 2 + 1 + 1 + 1 + 1 = 7 калорий. Можно показать, что это

минимальное количество энергии.

Для шестого участника (t₆= 23) оптимальным будет следующий алгоритм поражения целей:

1. Поразить цель в точке x₂= 0, потратив (2 - 0)²= 4 калории.

2. Переместиться в точку 2 + d = 5, потратив t₆= 23 калории.

3. Поразить цель в точке x₃= 7, потратив (7 - 5)²= 4 калории.

4. Поразить цель в точке x₁= 4, потратив (5 - 4)²= 1 калорию.

Суммарные затраты энергии равны 4 + 23 + 4 + 1 = 32 калории. Можно показать, что это

минимальное количество энергии.

Страница 8 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Задача 4. Лягушки на дереве

Ограничение по времени:

2 секунды

Ограничение по памяти:

1024 мегабайта

На ФТ Сириус можно наблюдать не только обыкновенных, но и дре-

весных лягушек, про некоторые виды которых известно, что они могут

менять свой цвет с зелёного на коричневый, и наоборот.

Как известно, дерево - это связный граф без циклов. В каждой вер-

шине дерева живёт ровно одна лягушка. Изначально все лягушки име-

ют зелёный цвет. Лягушки могут прыгать по дереву. За один прыжок

лягушка перемещается из вершины дерева, в которой она находится, в

соседнюю с ней по ребру вершину. После каждого прыжка цвет лягушки

меняется на противоположный.

Лягушки любят петь дуэтом. Дуэт обязательно должен состоять из

двух лягушек разного цвета. Чтобы две лягушки образовали дуэт, одна

из лягушек должна добраться до вершины, где живет другая лягушка, совершив при этом не более

d прыжков. Чтобы после перемещения цвет гостьи отличался от цвета хозяйки, гостья должна

сделать нечётное количество прыжков.

Необходимо определить, какое максимальное количество дуэтов лягушек может образоваться.

Каждая лягушка может входить только в один дуэт. Если вы правильно определите максимальное

количество дуэтов, вы получите частичный балл за подзадачу. Чтобы получить полный балл за

подзадачу необходимо также выяснить, какие пары лягушек должны образовать дуэты, чтобы их

оказалось максимальное количество.

Формат входных данных

Первая строка входных данных содержит одно целое число n (2 ⩽ n ⩽ 5 · 10⁵) - количество

вершин в дереве.

Вторая строка входных данных содержит одно целое нечётное число d (1 ⩽ d ⩽ n - 1) - макси-

мальное количество прыжков, которое может сделать одна лягушка на пути к другой.

Каждая из следующих n - 1 строк входных данных содержит два целых числа u и v

(1 ⩽ u, v ⩽ n) - номера вершин дерева, соединённых одним ребром. Вершины пронумерованы

от 1 до n.

Формат выходных данных

В первой строке выведите одно целое число m - максимально возможное количество дуэтов

лягушек, которые могут образоваться.

Если вы не хотите предъявлять сами пары, то выведите в следующей строке число -1 и завер-

шите работу программы.

Иначе, в следующих m строках выведите по два целых числа u_iи v_i- пару вершин, лягушки

из которых должны встретиться в одной из этих вершин и образовать дуэт, соблюдая описанные

выше правила.

Если максимальное количество дуэтов может быть образовано несколькими способами, выведите

любой из них.

Система оценивания

Если решение выводит не максимальное возможное количество пар или некорректный набор

пар на одном из тестов подзадачи, то оно получает 0 баллов за подзадачу. Если хотя бы на одном

тесте подзадачи решение выводит -1 вместо набора пар и на каждом тесте подзадачи выводит либо

верный набор пар, либо -1, то оно получает половину баллов за подзадачу. Если на каждом тесте

подзадачи решение выводит верный набор пар, то оно получает полный балл за подзадачу.

Страница 9 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Разбор задачи Лестница для участников олимпиады

Подзадача 1.

Переберем нижний левый угол лестницы, пусть это клетка (i, j). Заметим, что в столбце j мы

хотим максимизировать количество взятых клеток, так как это будет самый высокий столбец лест-

ницы.

Будемидти по столбцам от j направо, поддерживая высоту последнего столбца лестницы. Теперь

нам нужно найти максимальное количество клеток, которое можно набрать в текущий столбец, не

превышая высоту последнего столбца. Сделаем это наивно за O(h), получим решение за O(h²w²).

Подзадача 2.

Ускорим предыдущее решение, ускорив часть с наивным проходом вверх по таблице. Для этого,

предподсчитаем двумерный массив up_i,j, который будет означать количество подряд идущих единиц

в таблице, начиная с клетки (i, j) вверх. Это можно сделать динамическим программированием за

O(wh).

Теперь, когда мы перебираем столбец k в решении предыдущей подзадачи, мы можем за O(1)

вычислить высоту нового столбца, как минимум из up_i,kи высоты последнего столбца.

Получаем решение за O(h²w).

Подзадача 3.

√

Заметим, что min(h,w)

hw. Сделаем такое преобразование: повернем таблицу на 90 градусов

по часовой стрелке и развернем массив строк (строка i поменяется со строкой n - i). При таком

преобразовании количество строк и столбцов поменялось местами, а любая лестница изначальной

таблицы перешла в лестницу новой, и наоборот.

Тогда решим так: если h > w, то сделаем вышеописанное преобразование. Теперь верно, что

√

h w, значит решение из второй подзадачи работает за O(h²w) = O(hw min(h, w)) = O(hw

hw),

что укладывается в ограничения подзадачи.

Полное решение.

Для полного решения будем считать площадь лестницы с нижним левым углом в (i,j) с помощью

динамического программирования, назовем его dp_i,j. Найдем высоту первого столбца с помощью

массива up, как было описано во второй подзадаче. Теперь лестница устроена так: первые сколько-

то столбцов будут иметь высоту up_i,j, после чего высота уменьшится. Заметим, что столбец, где

первый раз высота уменьшится, это ближайший справа индекс k, такой что up_i,k< up_i,j.

Тогда верно, что dp_i,j= up_i,j(k - j) + dp_i,k. Осталось эффективно найти значения k для каж-

дой клетки таблицы, это стандартная задача нахождения ближайшего меньшего числа справа для

массива высот в каждой строке, которая решается за линейное время проходом со стеком.

Получаем решение за O(wh), которое проходит все подзадачи.

Разбор задачи Пересменка в Сириусе

Подзадача 1.

Если какой-то номер не закреплен ни за каким сотрудником, то ответ точно «NO». В первой подза-

даче это условие является и достаточным, достаточно направлять работников по убыванию l_i, а при

равенстве по убыванию r_i. Тогда все номера, которые за кем-то закреплены будут отремонтированы.

Подзадача 2.

Здесь можно перебрать все возможные порядки направления сотрудников в номера и просиму-

лировать процесс. Это можно сделать за O(k!kn).

Подзадача 3.

Здесь можно перебрать все подмножества номеров, которые уже отремонтированы по возраста-

нию битовой маски, поддерживая, можно ли добиться именно такого отремонтированного подмно-

жества. Если для достижимой маски перебрать, какого сотрудника надо сейчас направить. Если

обновлять маску с помощью битового или, то получится решение за O(2ⁿk).

Подзадачи 4 - 6.

Здесь нужны разные динамики по подотрезкам. Пусть dp_l,r- 0 или 1, в зависимости от того,

можно ли отремонтировать отрезок номеров с l-го по r-й и только его. Для подсчета dp_l,rпереберем

последнего работника, который что-то отремонтировал в этом сценарии. Пусть его номер i. Тогда

должно быть l l_iи r_i r и до его ремонта были отремонтированы все номера на отрезках [l, r^!] и

Страница 1 из 5

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

[l^!, r], где l_i- 1

r^!< m_iи m_i< l^!

r_i+ 1 (если l = l_iили r = r_i, то левого или правого отрезка

соответственно может и не существовать). То есть должно быть dp_l,r! = 1 и dp_l!_,r= 1.

Если для каждого l и r перебрать все возможные i, l^!и r^!, то получится решение за O(n⁴k).

Заметим, что l^!и r^!можно перебирать независимо. Тогда получится решение за O(n³k).

Вместо перебора l^!надо проверить, существует ли l^!в соответствующем полуинтервале, такое

что dp_l!_,r= 1. Для этого можно параллельно с полсчетом динамики насчитывать префиксные сум-

мы динамики по каждой из координат. То есть нас интересует pl_l,r= dp_l,r+ dpl+1,r + · · · + dp_r,r

и pr_l,r

= dp_l,r+ dpl,r-1 + · · · + dp_l,l. Тогда вместо перебора l^!и r^!можно проверить, что

prl,mi-1 - prl,li-2 > 0 и plmi+1,r - plri+2,r > 0. Тогда дополнительно ничего перебирать не надо и

решение работает за O(n²k).

Подзадача 7.

Здесь за каждым сотрудником закреплен префикс или суффикс номеров. Если есть два сотруд-

ника, за которыми закреплены префиксы номеров и они оба выполнили свои работы, то одного из

них можно было не направлять (того, у кого меньше префикс). Аналогично с суффиксами. То есть

достаточно вызвать только двух сотрудников: одного с префиксом и одного с суффиксом. Причем

два сотрудника, отрезки которых покрывают все номера не смогут оба отремонтировать свой отре-

зок только если у них обоих m_iлежит в пересечении их отрезков. Назовим таких двух сотрудников

противоречащими. То есть можно за O(k²) перебрать все пары и проверить.

Подзадачи 8, 9.

Условие этих подзадач на самом деле означало, что если отсортировать отрезки по возрастанию

l_i, то и l_iи r_iбудут строго возрастать, а еще каждый отрезок не будет целиком покрыт двумя

соседними. Назовем сотрудника полезным, если когда его направили в номер m_i, этот номер был не

отремонтирован (и сотрудник отремонтировал весь свой отрезок). Тогда в этих подзадачах каждый

сотрудник должен быть полезным. Для этого для каждой пары соседних сотрудников в порядке

сортировки по l_iв пересечении их отрезков должно лежать не более одного m_iэтих двух сотрудников

(иначе они ни в каком порядке не смогут оба быть полезными). Это условие является и достаточным,

если есть k сотрудников, то отрезков пересечения соседних не более k - 1, то есть для какого-то

сотрудника за его m_iбольше никто не ответственен и мы точно сможет направить его последним.

Можно его убрать, сделать всех остальных полезными рекурсивно и после этого направить его.

То есть в этой подзадаче надо проверить, что отрезки сотрудников покрывают все номера и что

соседние сотрудники не противоречат друг другу.

Подзадача 10.

Здесь тоже если отсортировать отрезки по неубыванию l_i, то r_iтоже будет неубывать, но уже

не обязательно делать всех сотрудников полезными. Рассмотрим полезных сотрудников в сценарии

где все номера отремонтированы. На самом деле тут тоже достаточно, чтобы никакие два соседних

сотрудника не противоречили друг другу. Если какой-то отрезок целиком покрыт двумя соседними,

то нетрудно видеть, что эти два соседних тоже не противоречат друг другу. То есть из того, что

никакие два соседних не противоречат друг другу следует, что можно выбрать их подпоследова-

тельность, в которой тоже соседние не противоречат и при этом выполняется условие предыдущей

подзадачи.

Отсюда получается динамическое программирование: dp_i- можно ли выбрать подпоследова-

тельность сотрудников в порядке возрастания l_j, заканчивающуюся i-м, покрывающую префикс

номеров такую, чтобы никакие два соседних сотрудника не противоречили друг другу. Пересчеты

можно сделать из всех i во все j с большей левой границей. Надо только проверить, что между со-

ответствующими отрезками нет дырки и что они не противоречат друг другу. Получается решение

за O(k²).

Подзадачи 11 - 13.

Заметим, что если среди полезных сотрудников есть вложенные отрезки, то внутреннего из

них можно было не вызывать. То есть чтобы получить общее решение достаточно в динамику из

предыдущей подзадачи добавить условие, что нельзя пересчитываться во вложенный отрезок. То

есть мы сортируем отрезки по l_iи пересчитываемся из i-го отрезка в j-й если верно следующее:

• r_j> r_i?: l_j- 1

Страница 2 из 5

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

• либо m_i< l_j, либо r_i< m_j

Получается динамика за O(k²). Также были менее эффективные решения с той же идеей, на-

пример O(nk).

Полное решение.

Теперь надо соптимизировать нашу динамику. Для пересчета в j-й отрезок подойдет любой

отрезок, идущий раньше него в порядке l_i, удовлетворящий условиям из предыдущей подзадачи.

То есть у него либо должно быть верно либо l_j- 1 r_i< r_jи при этом m_i< l_jлибо просто

l_j- 1

r_i< m_j. Если завести дерево отрезков на минимум, в котором после обработки i-го отрезка

мы ставим на позицию r_iминимум из того, что там уже стоит и m_i, то первый вариант условия

- как проверка, что на отрезке что-то есть (то есть

проверяется как минимум на отрезке, а второй

минимум < ∞). Теперь подсчет dp_jвыглядит как два запроса к дереву отрезков и одно обновление.

Итого решение работает за O(k log n + n). Также существовало решение, проверяющее условия с

помощью std::set.

Разбор задачи Сочи Парк

Подгруппы с x₀= 0

Если из точки x₀пойти вправо до точки x = x₀+ kd, то для всех целей, чья координата не

превосходит x (обозначим множество их индексов за L) оптимальное количество энергии равно

min(x_i% d, d - (x_i% d))². Обозначим сумму таких значений за left. Сумма оптимальных значений

для всех координат является решением 1 подгруппы.

Так же для всех целей, чья координата больше x (обозначим множество их индексов за R) посчи-

таем сумму квадратов координат и сумму координат. Обозначим их за right2 и right соответственно.

Тогда для фиксированной точки x = x₀+ kd ответ выглядит следующим образом:

)

f (k) = k · t +

(x - x_i)²= k · t + left +

)(x - x_i)2 = k · t + left + )(x2 - 2x · x_i+ x2

) =

i=1

i∈R

)

= k · t + left + x²· |R| - 2x ·

x_i+

x²

i∈R

= k · t + left + x²· |R| - 2x · right + right2

Если перебр\ть все возможные разумные расположения участника, то получится решение за

(

maxX

O mn ·

, проходящее подгруппу 4.

(

maxX

префиксными и суффиксными суммами. Тогда переборное решение работает за O m ·

проходит 6 подгруппу.

Для решения подгрупп 8, 12 и 14 заметим, что функция является выпуклой, воспользуемся

тернарным поиском по количеству перемещений. Чтобы определить конкретные значения left,

right и right2 воспользуемся бинарным поиском или std::lower_bound. Получим решение за

O(m log n · log maxX). Также для решения подгруппы 8 существует альтернативное решение с вло-

женными тернарными поисками за O(m log n · log²maxX).

Подгруппы с произвольным x₀

Очевидно, что оптимальные перемещения устроенны следующим образом: посетить несколько (воз-

можно, ноль) точек с мячами правее x₀, а затем посетить несколько (возможно, ноль) точек с

мячами левее x₀, или наоборот. При этом чтобы вернуться из части в начало, нужно потратить

столько же энергии, сколько на продвижение вперед. Поэтому можно воспринимать первую часть

пути с тратой 2t калорий.

Страница 3 из 5

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

Заменим все координаты на x_i- x₀, а x₀на 0. Пусть A = {x_i: x_i< 0}, B = {x_i: x_i> 0}. Далее

можно решать задачу независимо для каждой из частей аналогично решениям, описанным выше.

Итоговый ответ равен min(solve(A,t)+solve(B,2t),solve(A,2t)+solve(B,t)), где solve - решение для

x₀= 0.

Полные решения

Заметим, что существует не более чем O(n) позиций координат, в которых меняются значения left,

right и right2, поэтому можно найти с помощью тернарного поиска отрезок, на котором достига-

ется минимум, а затем найти минимум на этом отрезке вторым тернарным поиском. Асимптотика

O(m(log n + log maxX)). Для любого k из фиксированного отрезка все значения не изменяются

и можно вместо тернарного поиска найти вершину параболы по формуле и получить решение за

O(m log n), которое при аккуратной реализации набирает полный балл.

Для более оптимального решения рассмотрим производную функции f

f^!(k) = (k·t+left+x2·|R|-2x·right+right2)! = (k·t+left+(x0+kd)2·|R|-2(x0+kd)·right+right2)! =

= t + 2x₀d · |R| + 2kd²· |R| - 2d · right = t + 2kd²· |R| - 2d · right

Теперь можно для поиска отрезка, где достигается минимум, воспользовться бинарным поиском по

проиозводной и смотреть знак производной в точке k, а минимум искать формулой. Асимптотика

решения также O(m log n).

Разбор задачи Лягушки на дереве

Задача требует найти максимальное паросочетание в дерве, где вершины можно брать в пару,

если они находятся на нечётном расстоянии не превышающем d.

Подзадача 1.

Можно решить задачу перебором с рекурсией. Пусть текущее множество лягушек (вершин)

задано как {v₁, v₂, . . . , v_k}. Выбираем минимальную вершину и делаем два шага: либо исключаем её

из множества, либо подбираем к ней подходящую вершину, находящуюся на нечетном расстоянии не

более d, и удаляем обе из множества. Для проверки расстояний можно использовать любой алгоритм

поиска кратчайшего пути между всеми парами вершин. В зависимости от реализации асимптотика

может быть O(n!!) или O(2ⁿ· n).

Подзадача 2.

В этой подзадаче можно составлять пару из любых двух вершин, расстояние между которыми

нечетное. Заметим, что дерево является двудольным графом. Можно разделить вершины на две

доли, например, по четности расстояния до корня. Тогда максимальное паросочетание будет иметь

размер, равный минимуму размеров долей, а пары можно восстановить, выбирая любые вершины

из разных долей. Решение работает за O(n).

Подзадача 3.

Эта подзадача сводится к стандартной задаче нахождения максимального паросочетания в де-

реве. Решение можно получить либо с помощью динамического программирования по поддеревьям,

либо с использованием жадного алгоритма.

Подзадача 5.

Здесь достаточно явно построить двудольный граф, в котором две вершины соединены ребром,

если они находятся на нечетном расстоянии не более d. После этого можно применить алгоритм

поиска максимального паросочетания в двудольном графе, например, алгоритм Куна.

Подзадачи 4, 6-8

В этих подзадачах требуется разработать алгоритм с асимптотикой O(nd). Основная идея -

использование жадного алгоритма. При стандартном поиске в глубину мы пытаемся объединить

некоторые свободные вершины из поддерева в пару. Если вершины находятся на расстояниях x

и y от текущей вершины, то их можно объединить, если x + y d и они различной четности.

Однако наивный жадный подход, который объединяет все такие пары, не работает. Чтобы улучшить

алгоритм, заметим, что если x+y < d и вершины различной четности, то их можно будет объединить

выше, а не на данной вершине. Таким образом, в каждой вершине следует объединять только те

Страница 4 из 5

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, первый тур

Сириус, 27 марта 2025 года

пары, у которых сумма расстояний равна d. Для этого достаточно хранить множества вершин из

поддерева на каждой глубине до d от текущей вершины (например, в двусвязном списке). На каждой

вершине мы жадно объединяем пары, расстояние между которыми в сумме равно d. Однако в

корневой вершине необходимо запустить отдельный алгоритм жадного поиска, который для каждой

вершины подбирает пару с максимально возможным расстоянием до корня.

В зависимости от реализации, можно получить решение за O(nd²) или O(nd).

Полное решение.

Чтобы ускорить алгоритм из предыдущей подзадачи, можно использовать структуру данных

для поддержки множества расстояний до текущей вершины для каждой доли, при этом хранить

только те расстояния, где еще есть свободные вершины. Также необходимо эффективно определять

высоту, на которой в множестве расстояний присутствует пара с суммой d. Для каждого хранимого

расстояния x можно поддерживать максимальное y такое, что x + y d. При этом добавлять в

множество событий высоту, на которой пара даёт сумму d. При аккуратном слиянии таких структур

и обновлении событий общее решение будет работать за O(nlogn).

Страница 5 из 5

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Общая информация по задачам второго тура

Задача

Тип задачи

Ограничения

5. Качественный отдых

стандартная

1 с, 1024 МБ

6. Лягушки на болоте

стандартная

1 с,

128 МБ

7. Минимизация инверсий

стандартная

1 с, 1024 МБ

8. Жизнь программистов

стандартная

2 с, 1024 МБ

Необходимо считывать данные из стандартного потока ввода. Выходные данные необходимо

выводить в стандартный поток вывода.

Баллы за подзадачу начисляются только, если все тесты этой и необходимых подзадач пройде-

ны. Решение запускается на тестах для определенной подзадачи, если все тесты всех необходимых

подзадач пройдены.

Во всех подзадачах каждой задачи во время тура вам показываются баллы за подзадачу, если

все тесты пройдены, либо первая ошибка и номер теста.

Для некоторых подзадач может также требоваться, чтобы были пройдены все тесты из условия.

Для таких подзадач указана дополнительно буква У.

Страница 1 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Задача 5. Качественный отдых

Ограничение по времени:

1 секунда

Ограничение по памяти:

1024 мегабайта

Прохор проходит стажировку продолжительностью n календарных

дней в ИТ-компании. Прохор стажируется в службе поддержки, поэтому

у него сложный график рабочих и выходных дней на время стажировки.

Кромевыходных, уПрохора есть некоторое количество отгулов - до-

полнительных выходных дней, которые он может взять в любые рабочие

дни.

За один выходной день Прохор качественно отдохнуть не сможет,

поэтому он считает днями качественного отдыха только те выходные

дни, которые входят в последовательность из идущих подряд двух или

более выходных дней.

Вам даны q запросов - различных значений количества отгулов, ко-

торые может взять Прохор. Ваша задача - по заданному графику рабочих и выходных дней стажи-

ровки определить для каждого запроса, какое максимальное количество дней качественного отдыха

за время стажировки может получить Прохор.

Формат входных данных

Первая строка входных данных содержит два целых числа n и q (1 :( n :( 100 000, 1 :( q :( n + 1).

Следующая строка содержит строку s длины n, состоящую из символов «0» и «1» - график

стажировки. В этой строке символом «0» обозначается рабочий день, а символом «1» - выходной.

В следующих q строках находятся q целых чисел k_i(0 :( k_i:( n) - количество отгулов в i-м

запросе. Гарантируется, что каждое значение k_iне превосходит количества рабочих дней в графике

стажировки.

Формат выходных данных

Выведите q целых чисел - для каждого значения k_iопределите наибольшее количество каче-

ственных дней отдыха, которое может получить Прохор за время стажировки, выбрав k_iдополни-

тельных выходных дней.

Система оценивания

Дополнительные ограничения

Необх.

Подзадача

Баллы

подзадачи

дополнительно

Все дни графика - рабочие

Выходные и рабочие дни

чередуются, первый день

стажировки - выходной

q = 1

k₁= 0

q = 1

k₁= 1

n :( 15

n :( 1000

У, 5

В графике нет двух выходных подряд

1, 2

У, 1-7

Страница 2 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Задача 6. Лягушки на болоте

Ограничение по времени:

1 секунда

Ограничение по памяти:

128 мегабайт

В Сочи при подготовке Олимпиады-2014 была завезена самшитовая

огнёвка (небольшая бабочка с Дальнего Востока). Она уничтожила сам-

шитовую рощу, поэтому древесным лягушкам теперь приходится жить

на болоте. Но они сохранили способность после прыжка менять свой

цвет с зелёного на коричневый и наоборот.

Болото представляет собой плоскость, в некоторых точках которой

располагаются кочки. Размером кочек можно пренебречь и считать их

точками на плоскости. За один прыжок лягушка может перепрыгнуть

с кочки, на которой она находится, на любую другую кочку, которая

находится от неё на расстоянии не более r. После каждого прыжка цвет

лягушки меняется на противоположный. Прыгать на месте лягушка не

умеет.

Вам необходимо для каждой стартовой кочки лягушки от 1 до n определить, может ли она,

совершив некоторое количество прыжков, вернуться на стартовую кочку, поменяв при этом свой

цвет.

Формат входных данных

Первая строка содержит два целых числа n и r (2 :( n :( 10⁵, 1 :( r :( 10⁹) - число кочек на

болоте и расстояние, на которое прыгает лягушка.

Каждая из следующих n строк описывает расположение кочек. В i-й из них содержатся два

целых числа x_iи y_i(0 :( x_i, y_i:( 5 · 10⁸) - координаты i-й кочки.

Никакие две кочки не располагаются в одной точке.

Формат выходных данных

Выведите строку, состоящую из n символов. Если лягушка, стартовав с кочки i, может вернуться

на неё, имея противоположный цвет, i-й символ должен быть «1», а иначе - «0».

Система оценивания

Подзадача

Баллы

Дополнительные ограничения

Необх. подзадачи

n :( 3

n :( 200

У, 1

У, 1, 2

n :( 1 000

n :( 10 000

У, 1-3

y_i= 0

r :( 2

r :( 4

r :( 10

У, 6, 7

(x_i- x_j)²+ (y_i- y_j)²

, i /= j

У, 6

У, 1-9

Страница 4 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Задача 7. Минимизация инверсий

Ограничение по времени:

3 секунды

Ограничение по памяти:

1024 мегабайта

Дана таблица a, состоящая из r строк и c столбцов, в которой записаны в произвольном порядке

все различные числа от 1 до r·c. Элементы этой таблицы переносятся в изначально пустой массив b.

Пока таблица непустая, над ней выполняется одно из двух действий:

• Дописать в конец массива элементы первой строки таблицы в порядке от элемента в первом

столбце до элемента в последнем и удалить первую строку из таблицы.

• Дописать в конец массива элементы первого столбца таблицы в порядке от элемента в первой

строке до элемента в последней и удалить первый столбец из таблицы.

Порядок действий требуется выбирать таким, чтобы количество инверсий в полученном массиве

после применения всех операций было минимальным.

Инверсией называется такая пара индексов элементов массива 1 :( i < j :( r · c, что b_i> b_j.

Формат входных данных

Первая строка содержит два целых числа r и c (r :( c, 1 :( r · c :( 2 000 000) - количество строк

и столбцов в таблице соответственно.

В следующих r строках содержится описание таблицы a. В i-й из них содержится c целых чисел

ai1, . . ., a_ic(1 :( a_ij:( r · c) - элементы матрицы a.

Гарантируется, что все числа в таблице a различны.

Формат выходных данных

Выведите одно число - минимально возможное количество инверсий в массиве b после приме-

нения всех операций.

Страница 6 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Система оценивания

Ограничения

Необходимые

Подзадача

Баллы

подзадачи

r · c

r + c :( 14

У, 1

r · c :( 500

Все строки и столбцы отсортированы в

возрастающем порядке и r · c :( 250 000

r = 1

r · c :( 250 000

r :( 2

У, 1, 4, 5

r :( 20

r, c :( 100

У, 1

r · c :( 10 000

У, 1, 2, 7

c :( 1000

c :( 2500

У, 1, 2, 7, 9

c :( 5000

У, 1, 2, 7, 9, 10

r :( 100

У, 1, 2, 7, 9-11

c :( 7500

У, 1, 2, 7-12

c :( 10 000

c :( 15 000

У, 1, 2, 7-13

У, 1, 2, 7-14

c :( 20 000

У, 1, 7

r, c :( 200

r, c :( 400

У, 1, 7, 16

r, c :( 600

У, 1, 2, 7, 16, 17

У, 1, 2, 7, 16-18

r, c :( 800

r, c :( 1000

У, 1, 2, 7, 9, 16-19

r, c :( 1200

У, 1, 2, 7, 9, 16-20

У, 1, 2, 7, 9, 16-21

r, c :( 1400

У, 1, 2, 7-9, 16

r · c :( 100 000

r · c :( 250 000

У, 1-10, 16, 17, 23

У, 1-11, 16-18, 23, 24

r · c :( 500 000

–

У, 1-12, 16-19, 23-25

r · c :( 750 000

r · c :( 1 000 000

У, 1-13, 16-20, 23-26

У, 1-14, 16-21, 23-27

r · c :( 1 500 000

У, 1-28

Страница 7 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Задача 8. Жизнь программистов

Ограничение по времени:

2 секунды

Ограничение по памяти:

1024 мегабайта

Новый сериал про жизнь программистов содержит

n серий, пронумерованных от 1 до n. Телекомпания Си-

риус ТВ планирует показывать серии по очереди от

первой до последней в течение k дней, каждый день

показывая блок из одной или нескольких подряд иду-

щих серий. Каждая серия будет показана ровно один

раз.

По результатам тестовых просмотров маркетоло-

ги компании составили рейтинг серий: i-й серии со-

поставлено число a_iот 1 до n, самая интересная се-

рия получила рейтинг 1, а самая скучная - рейтинг n.

Рейтинги различных серий различны, поэтому числа

[a₁, a₂, . . . , a_n] образуют перестановку.

Пусть принято решение о том, в какой день какие серии будут показаны. Для каждого дня

определим рейтинг этого дня, равный рейтингу самой скучной серии этого дня. Иначе говоря, пусть

в j-й день показываются серии с l_jпо r_j, тогда рейтинг этого дня b_jравен максимальному значению

среди [alj , alj +1, . . . , arj ].

Чтобы показ сериала был удачным, необходимо вовлечь зрителей в просмотр. Среди всех воз-

можных способов разбить серии на k блоков по дням необходимо выбрать тот, в котором рейтинг

первого дня как можно лучше: b₁минимально. Среди этих способов в свою очередь необходимо

минимизировать рейтинг второго дня b₂, при выбранных значениях b₁и b₂- минимизировать b₃,

и так далее. Таким образом, необходимо разбить показ серий на k блоков таким образом, чтобы

лексикографически минимизировать последовательность [b₁, b₂, . . . , b_k].

Вам необходимо ответить на q запросов, каждый из которых задаётся двумя числами: k и i.

В качестве ответа на запрос необходимо вывести значение b_i- рейтинг i-го дня для оптимального

способа показать сериал за k дней.

Формат входных данных

В первой строке входных данных содержится два целых числа n и q (1 :( n, q :( 300 000) -

количество серий и количество запросов соответственно.

Во второй строке входных данных содержатся n целых чисел a₁, a₂, . . . , a_n(1 :( a_i:( n) -

рейтинги серий. Гарантируется, что массив a является перестановкой целых чисел от 1 до n.

Следующие q строк содержат по два целых числа k и i (1 :( i :( k :( n) - параметры очередного

запроса.

Формат выходных данных

В q строках выведите ответ на каждый запрос, в том порядке, в котором они даны во входных

данных.

Примеры

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

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

7 4

6 4 2 3 1 7 5

7 4

1 1

4 2

5 3

3 1

2 3 1

2 2

Страница 9 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Замечание

Рассмотрим первый тест:

• При k = 7 существует единственный способ показа: каждый день показывать по одной се-

рии. Рейтинги серий по дням получаются [6], [4], [2], [3], [1], [7], [5], откуда b = [6, 4, 2, 3, 1, 7, 5],

поэтому ответ на запрос k = 7 и i = 4 равен b₄= 3.

• При k = 1 существует единственный способ показа: показать все серии в первый день. Рейтинги

серий по дням: [6, 4, 2, 3, 1, 7, 5], откуда b = [7], поэтому ответ на запрос k = 1 и i = 1 равен

b₁= 7.

• При k = 4 оптимально в первый день показать четыре серии, а затем три дня показывать по

одной серии. Рейтинги серий по дням: [6, 4, 2, 3], [1], [7], [5], откуда b = [6, 1, 7, 5], поэтому ответ

на запрос k = 4 и i = 2 равен b₂= 1.

• При k = 5 оптимально в первый и последний день показать по две серии, а в остальные дни

по одной. Рейтинги серий по дням: [6, 4], [2], [3], [1], [7, 5], откуда b = [6, 2, 3, 1, 7], поэтому ответ

на запрос k = 5 и i = 3 равен b₃= 3.

Система оценивания

Доп. ограничения

Необх.

Подзадача

Баллы

подзадачи

дополнительно

n :( 20

k = 2

k = 3

Перестановка имеет вид

1, n, 2, n - 1, . . .

n :( 200

У, 1

n :( 3000

У, 1, 5

Количество различных

значений k во всех

У, 2, 3

запросах не больше 10

i :( 3

Количество значений i,

таких что a_i< ai+1, не

У, 1

больше 20

Количество значений i,

таких что a_i> ai+1, не

У, 1

больше 20

Перестановка была

выбрана случайно

n :( 10⁵

У, 1, 5, 6

У, 1-12

Страница 10 из 10

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Разбор задачи Качественный отдых

В этой задаче отдельно нужно рассмотреть первую группу, когда все дни в графике выходные.

Тогда при k = 0 или k = 1 ответ равен 0, а при k

2 ответ равен k.

Во всех остальных случаях заметим, что каждый добавляемый выходной день всегда можно сде-

лать днём качественного отдыха, если он будет соседствовать с каким-то другим выходным днём,

поэтому каждый отгул увеличивает количество дней качественного отдыха как минимум на 1. Но

если есть два изолированных выходных днях, между которыми есть один рабочий день, то взяв

отгул в этот рабочий день количество дней качественного отдыха увеличивается на 3 - два су-

ществующих выходных и один новый. Разобьём все отдельные выходные дни на пары соседних,

посчитаем количество таких пар n₃. Также посчитаем отдельные выходные дни, не вошедшие в эти

пары n₂, и количество выходных дней, которые уже являются днями качественного отдыха.

Ответ для каждого данного k получается жадным алгоритмом. Сначала нужно выбирать отгу-

лы между парой изолированных выходных дней, что увеличивает количество качественных дней

отдыха на 3, таких отгулов может быть не более, чем n₃. Следующие отгулы будем выбирать так,

чтобы они увеличивали количество дней качественного отдыха на 2, присоединяя их к изолиро-

ванным выходным дням, не вошедшим в пары. Каждый такой отгул будет увеличивать число дней

качественного отдыха на 2, и таких отгулов может быть не более n₂. Каждый из оставшихся отгулов

увеличивают ответ на 1.

Если заранее подсчитать значения n₃, n₂и уже существующих дней качественного отдыха, то

можно отвечать за один запрос за O(1) и суммарная сложность будет O(n + q).

Разбор задачи Лягушки на болоте

В задаче просят для каждой вершины графа построенного на точках ответить на вопрос: правда

ли она лежит в не двудольной компоненте связности?

Подзадача 1.

Так как компонента связности не двудольная тогда и только тогда, когда в ней есть цикл нечет-

ной длины, в этой подзадаче можно было проверить это любым полным перебором.

Подзадача 2.

В этой подзадаче можно обойти граф и раскрасить его в 2 цвета из каждой вершины за время

O(n²). Граф можно было построить в явном виде.

Подзадача 3.

Здесь подойдет построение графа за O(n²) и любой обход за O(n²). Граф можно было построить

в явном виде.

Подзадача 4.

Здесь требуется с оптимизировать решение из предыдущей группы по памяти. Самый простой

способ это сделать - не хранить граф в явном виде.

Подзадача 5.

В этой подзадаче все точки на одной прямой. Можно показать, что в таком случае необходимо

и достаточно проверить нужно ли провести ребра в 2 ближайших точки слева и справа в порядке

сортировки по этой прямой. Затем обойти полученный граф за O(n + m). Так как ребер будет O(n)

время работы решения O(n) + O(sort).

Подзадачи 6-8.

В этих подзадачах можно обойти граф за O(n · r²) рассматривая только точки на расстоянии

не более r от текущей. В зависимости от эффективности реализация может набирать от 5 до 15

баллов.

Подзадача 9.

То что точки находятся на достаточно большом расстоянии гарантирует, что в графе линейное

количество ребер. Для его построения воспользуемся следующей техникой: разобьем плоскость на

квадраты со стороной r/2. Распределим точки по квадратам, в которые они попадают. Для каждой

точки рассмотрим все точки попадающие в квадраты находящиеся на + - r по x и y от квадрата в

котором она находится. Так как в каждом квадрате не более 2 точек, построение графа работает за

O(n) или O(n·log(n)) в зависимости от выбранного способа сохранения точек в квадратах. Обходить

граф буде так же, как и в 5й подзадаче.

Страница 1 из 6

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

Полное решение.

Чтобы получить полный балл за задачу нужно объединить идеи предыдущих групп. Воспользу-

емся построением графа из 9й подзадачи и идеей из 5й подзадачи о том что достаточно проводить

ребра в небольшое число соседей. Разобьем квадраты с точками на тяжелые, такие в которых хотя

бы 3 точки и лёгкие, в которых менее 3. Если точка лежит в тяжелом квадрате, ответ для нее,

очевидно, 1. Если точка лежит в легком квадрате, проведем из нее рёбра аналогично технике из 9й

подзадачи. Так как для каждой клетки есть не более 25 ∗ 2 точек из которых попробуют провести

ребра в точки в ней, суммарно будет проведено O(n) ребер. Для того, чтобы для решения было

достаточно обойти граф аналогично предыдущим подзадачам, проведем петли для всех вершин в

тяжелых клетках. Итого O(n) или O(n · log(n)) времени на построение и O(n) на обход графа.

Разбор задачи Минимизация инверсий

Обозначим за M[a:b][c:d] подматрицу с левым верхним углом в (a, c) и правым нижним в (b, d).

Идея динамического программирования

Пусть dp[i][j] - ответ для прямоугольника с левым верхним углом в (i, j) и правым нижним в

(n, m).

Если первым действием была удалена первая строка, то минимальное количество инверсий в ито-

говом массиве это D[i][j] + dp[i + 1][j], где D[i][j] - количество инверсий внутри M[i:i][j:m]

плюс количество инверсий между M[i:i][j:m] и M[i+1:n][j:m] (то есть количество инверсий внут-

ри удалённой части плюс количество инверсий, которые удалённая часть образует с оставшейся

подматрицей).

Аналогично, если первым действием был удалён первый столбец, то минимальное количество ин-

версий в итоговом массиве это R[i][j] + dp[i + 1][j], где R[i][j] - количество инверсий внутри

M[i:n][j:j] плюс количество инверсий между M[i:n][j:j] и M[i:n][j+1:m].

При известных D[i][j] и R[i][j] динамика тривиально пересчитывается за O(nm).

Решение за O(n²m²(n + m))

Значения D[i][j], R[i][j] могут быть вычислены напрямую из определения. Для вычисления од-

ного значения нужно перебрать пару элементов внутри удаляемой строки/столбца (не более n²+m²

пар для одного значения) и пару из элемента удаляемой строки/столбца и элемента оставшейся под-

матрицы (не более nm(n + m) пар для одного значения). Всего нужно вычислить 2nm значений.

Итого время работы: O(nm · (n²+ m²+ mn(n + m))) = O(n²m²(n + m)).

Решение за O(n²m²)

Можно действовать оптимальнее:

• Для вычисления числа инверсий внутри строки/столбца вычислять только разницу соседних

значений. Одна разница вычисляется за линию от размера, поэтому суммарно на эту часть

будет потрачено O(nm(n + m)) времени. Можно оптимизировать эту часть деревом Фенвика,

тогда получится O(nm log(nm)) времени на всю таблицу, но в этой подгруппе это не нужно.

• Подсчёт числа инверсий между удаляемой строкой/столбцом можно сделать за O(nm). До-

статочно насчитать массив префиксных сумм массива подсчёта одной из частей и пройтись по

другой. Каждое из действий выполняется за O(nm).

Решение за O(n²m log(nm))

Оптимизируем предыдущее решение деревом Фенвика. Будем сразу считать все значения D[i][j],

R[i][j] для строки. Для этого пройдёмся вдоль длинной стороны (чтобы пересчёт работал за длину

Страница 2 из 6

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

короткой), поддерживая массив подсчёта каждой из частей в дереве Фенвика и вычисляя разницу

значений за O(количество добавленных элементов).

• Для R[i][j] пройдёмся по строкам, поддерживая остающуюся часть в дереве Фенвика, и

вычисляя число инверсий удаляемого столбца проходом по нему. Суммарно будет произведено

O(n²m) запросов прибавления и O(n²m) запросов суммы на префиксе.

• Для D[i][j] пройдёмся по строкам, поддерживая обе части в дереве Фенвика. После каждого

добавления аналогично вычислим число инверсий, образованных только что добавленными

элементами (новым элементом удаляемой строки и новым столбцом оставшейся подматрицы)

Здесь будет использоваться два дерева Фенвика, к одному будет произведено O(nm) запросов

прибавления и O(n²m) запросов суммы на префиксе, а к другому O(n²m) запросов прибавле-

ния и O(nm) запросов суммы на префиксе.

Можно добиться существенного ускорения, оптимизировав вторую часть: использовать не дерево

Фенвика, выполняющее оба типа запросов за O(log nm), а корневую, которая выполняет один тип

запросов за O(1), а другой за O(√nm).

Идея симметричного решения

Рассмотрим разницу R[i][j] - R[i + 1][j]. Это в точности количество инверсий между элемен-

том (i, j) и M[i:n][j:m], плюс количество инверсий между M[i+1:n][j:j] и M[i:i][j+1:m]. Обо-

значим первое за C[i][j], второе за I[i][j].

Заметим, что разница D[i][j] - D[i][j + 1] тоже вычисляется аналогичным образом через

C[i][j] и I[i][j]. Только вместо I[i][j] нужно использовать (n - i)(m - j) - I[i][j], то есть

количество пар, которые не образуют инверсию для I[i][j] (мы вычли количество пар элементов,

образующих инверсию, из количества всех пар элементов).

Обратите внимание, что значений C[i][j], I[i][j] достаточно для вычисления R[i][j] и

D[i][j] за O(nm). Никаких дополнительных тяжёлых (асимптотически больших O(nm)) вычис-

лений производить не нужно. Причём значения I[i][j] считаются один раз.

Решение за O(nm(n +

^√nm))

• Значения C[i][j] можно вычислить сканлайном по значениям с 2d деревом Фенвика за

O(nm log n log m)

• Значения I[i][j] можно вычислить аналогично проходу по строкам из решения за

O(n2m log(nm)). Только на этот раз будет O(nm) запросов изменени√и O(n2m) запросов сум-

мы на префиксе, что позволяет реализовать эту часть за O(nm(n +

nm)).

Оптимизация C[i][j]

Заметим, что с помощью C[i][j] учитываются инверсии, которые будут присутствовать в итоговом

массиве вне зависимости от порядка операций. Так как если клетка a была не левее и не выше клетки

b, то клетка a будет идти после клетки b в итоговом массиве.

Можно вычислить суммарно число инверсий по всем таким парам клеток за O(nm log(nm)):

• Выпишем табличку по строкам, по столбцам и посчитаем суммарное число инверсий в двух

полученных массивах.

• Рассмотрим пару клеток a, b. Если ни одна из них не была (не строго) левее и выше другой,

то в одном массиве a будет идти перед b, а в другом наоборот. Значит от этой пары клеток мы

получим ровно одну инверсию к итоговой сумме. Заметим, что таких пар в точности C²· C².

Если же одна была (не строго) левее и выше другой, то если они образовывали инверсию, то

Страница 3 из 6

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

эта инверсия будет учтена два раза в итоговой сумме. Значит мы можем вычислить количество

таких пар, образующих инверсию, просто вычтя из общего количества посчитанных инверсий

число C²C2 и разделив полученную разницу на два. Это в точности количество инверсий,

n m

которые гарантированно (в не зависимости от порядка удаления строк и столбцов) будут в

итоговой последовательности.

Решение за O(nm (n +

^√m))

Решение за O(nm(n +

^√nm)) имеет существенную константу, так как в нём осуществляется O(n²m)

обращений к корневой, каждое из которых работает за O(1), но является обращением к случайному

месту в памяти.

Будем делать сканлайн по значениям в матрице. При обработке значения в клетке (i, j) хо-

тим учесть все инверсии, которые оно образовало в I[i-1][j], I[i-2][j], ..., I[0][j]. Пусть

T[i][j] - 0, если элемент (i, j) ещё не был обработан, и 1 иначе. Пусть P[i][j] - суффиксные

суммы T[i][j] в строках. Тогда вклад значения (i, j) в I[i-1][j] это в точности P[i-1][j], вклад

в I[i - 2][j] это P[i -

2][j], аналогично для I[i-3][j], ..., I[0][j].

Если хранить матрицу по столбцам (то есть так, чтобы столбцы лежали последовательно в

памяти), то операцию пересчёта значений I[i-1][j], I[i-2][j], ..., I[0][j] это поэлементное

прибавление последовательного отрезка в памяти к другому последовательному отрезку в памя-

ти. Что имеет сильно меньшую константу, чем обращение к случайному элементу (в пересчёте на

элемент).

Значения P[i][j] можно поддерживать явно, обновляя за O(m) при обработке элемента мат-

рицы. Эта часть не может быть одновременно с предыдущей последовательной в памяти (так как

это требует хранения матрицы по ст√кам). Но можно хранить значения P[i][j] в корневой, тогда

обновление будет происходить за O(

m), что сделает её асимптотически легче предыдущей части

при n ≈ m.

Так как мы сделали самую асимптотически тяжёлую часть решения оптимальнее по константе,

то всё решение будет работать значительно быстрее.

√

Решение за O(nm (k · n + k

^km))

Вместо двухуровневой корневой будем использовать k-уровневую.

При почти квадратной табличке оптимально взять k = 2, при существенно отличающихся из-

мерениях стоит взять большее k, например можно просто брать k = 4 (или использовать одно из

предыдущих решений). Конкретный выбор не сильно важен, так как случай квадратной таблички

самый тяжёлый.

Разбор задачи Жизнь программистов

В 1-й группе n

20, поэтому в ней достаточно перебрать все разбиения и найти оптимальное

для каждого k.

Во 2-й группе k = 2. В ней можно просто перебрать разбиение за O(n) и выбрать оптимальное.

Но можно заметить более важное для последующих подгрупп замечание: если первый элемент мак-

симальный, то оптимально в первый отрезок взять все элементы без последнего, а иначе оптимально

взять в первый отрезок только первый элемент.

В 3-й группе k = 3. Достаточно перебрать первый отрезок и оптимальным образом разбить

оставшийся суффикс. Для этого достаточно использовать идею из предыдущей группы.

В 5-й подгруппе можно написать динамику за O(n³), а именно пусть dp[i][j] - минимальный

лексикографический массив, который можно получить, разбив префикс [a₁, a₂, . . . , a_i] на j отрез-

ков. Переходы - это или начать новый отрезок ai+1 элементом, или прорелаксировать максимум

последнего подотрезка этим элементом.

Перейдем к ключевой идее в задаче, а именно, как для фиксированного k быстро получать оп-

тимальное разбиение. Добавим обозначение greater[i] - первая позиция j > i, такая что a[j] > a[i].

Если такой позиции нет, то greater[i] = n (всё в 0 индексации). Будем жадно набирать разбиение

Страница 4 из 6

Тридцать седьмая всероссийская олимпиада по информатике, заключительный этап, второй тур

Сириус, 29 марта 2025 года

слева направо. Пусть в текущий момент нужно разбить суффикс i на k отрезков. Если k = 1, то по-

следний отрезок уже определён. Если k = 2, то оптимально брать отрезок [i, min(n-1, greater[i])-1].

Иначе, пусть в разбиение будет взят отрезок [i, j - 1]. Так как k

3 максимум на следующем от-

резке равен a_j. Максимум на первом отрезке равен a_i, поэтому на j накладываются следующие

ограничения:

• j

greater[i], так как иначе максимум на первом отрезке будет неправильным.

• j

n - k + 1, так как иначе в оставшемся суффиксе нельзя будет уместить оставшийся k - 1

отрезок.

Таким образом, в качестве оптимального j выгодно взять минимум на отрезке от i + 1 до

min (n - k + 1, greater[i]). Это можно реализовать за O(n log n) или за O(n) для каждого k, что

достаточно, чтобы сдать 6-ю подгруппу. С помощью данной идеи можно также сдать 7-ю и 8-ю

группы.

Далее есть два пути. В первом из них можно просто переходить от оптимального разбиения

для k отрезков к оптимальному для (k + 1)-го. Разберёмся как именно отличаются оптимальные

разбиения для k и k + 1. Сначала у них будут совпадать все подотрезки, а потом в какой-то момент,

либо жадник для k придет в состояние, когда надо брать 1 или 2 отрезка, либо граница допустимого

j из текущего i увеличится на один, из-за чего можно будет получить новый минимум. Если мы

берем этот новый минимум, то это означает, что все следующие отрезки будут единичной длины.

Скажем, что подотрезок (переход) длинный, если его длина больше единицы, и подотрезок (переход)

короткий, если его длина один. Будем следить за всеми длинными подотрезками при изменении

k + 1 → k, какие-то длинные подотрезки удаляются, и добавляется не более одного, то есть всего их

O(n) для всех k.

Если сжимать все короткие подотрезки и эффективно их находить, то можно написать решение,

работающее O((n+q) log n), так как сжатых коротких отрезков будет линейно. Их можно эффектив-

но находить с помощью дерева отрезков и сетов. Но данная реализация не является самой простой.

Второй путь следующий: мы так же для всех k отдельно построим массив за O(n). Для этого мы

не будем искать минимум на отрезке, а будем переходить к ближайшему справа меньшему элементу,

пока он левее чем greater[i] и n - k + 1.

Теперь будем строить ответ параллельно для всех k. Для этого напишем функцию

solve(pos, lk, rk), которая предполагает, что префикс перестановки до pos разбит на подотрезки и

это разбиение оптимально для всех k от lk до rk. Сначала отдельно обработаем случай разбиения

суффикса начиная с pos на один или два отрезка. Теперь будем параллельно эмулировать жадник

для всех оставшихся k на интересном отрезке. Для этого сначала посмотрим на все возможные раз-

резы, перебрав цепочку ближайших справа меньших элементов. Каждый разрез оптимальный для

какого-то отрезка значений k, поэтому можно запуститься рекурсивно.

Если реализовать эту идею наивно, то параллельное построение массивов для всех k будет ра-

ботать за O(n²). Но можно применить следующую оптимизацию: в рекурсии можно найти макси-

мальный возрастающий подотрезок начинающийся в pos и добавить сразу много отрезков длины 1

в сжатом виде. Структуру, умеющую добавлять сразу много отрезков длины 1 и отвечать на k-й

элемент, можно реализовать обычным стеком и для ответа на запрос использовать бинпоиск. Такая

оптимизация позволяет сдать 10-ю группу.

Можно заметить, что rk всегда равно n - pos, поэтому чтобы сдать 9-ю группу достаточно

отдельно обработать случай, когда суффикс разбивается только на единичные отрезки. Замечание

про rk нужно для полного решения.

Давайте заметим, что решение бы работало быстро, если бы при каждом рекурсивном запуске

отрезок [lk, rk] разделялся, так как таких разделений не может больше чем n - 1. В случайной

перестановке ожидаемо каждое разделение происходит быстро, поэтому такое решение работает

быстро, если эффективно обрабатывать суффикс отрезков длины 1.

Чтобы перейти к полному решению достаточно эффективно находить следующий момент рекур-

сии, когда отрезок [lk, rk] разделится. Так как rk = n-pos + 1, чтобы найти ближайшее разделение,

достаточно найти минимальное j

pos, что для некоторых k из отрезка [lk, rk] будет эффективнее

Страница 5 из 6

Информатика (с ответами). Всероссийская олимпиада школьников в Москве (2024-2025 год) - часть 3