Автор Заключительный этап 2025 всероссийской олимпиады школьников по информатике задания, ответы и решения для 9, 10, 11 класса. Данная олимпиада прошла у финалистов 25-30 марта 2025 года в Сириусе. Индивидуальные результаты участников заключительного этапа всероссийской олимпиады школьников вы можете посмотреть на официальном сайте.
Задания олимпиады первого тура
informatika-1den-zakl-vos-2025Задания олимпиады второго тура
informatika-2den-zakl-vos-2025Ответы и решения заданий
reshenie-inf-vos-2025-zadanieЗадача 1. Лестница для участников олимпиады
В ОЦ «Сириус» любимым местом для сбора и неформального общения школьников служат различные лестницы. Но количество участников олимпиады по информатике значительно превосходит количество участников любой образовательной программы, и подходящей для них лестницы среди имеющихся не нашлось, поэтому служба оснащения решила построить новую лестницу, используя специальную заготовку. Заготовка представляет собой таблицу из h строк и w столбцов, пронумерованных сверху вниз и слева направо соответственно. В каждой клетке таблицы записано одно число — ноль или единица.
Лестницу можно сделать только из тех клеток таблицы, в которых записана единица. Полученная лестница образуется из множества клеток, в которых записана единица, находящихся в нескольких последовательных строках таблицы. Множество выбранных клеток в каждой строке лестницы должно быть непрерывным отрезком. При этом в каждой следующей строке, входящей в лестницу, должно быть выбрано не меньше клеток, чем в предыдущей, находящейся непосредственно над нею, строке, а самые левые выбранные клетки в каждой строке должны располагаться в одном и том же столбце. Ниже приведен пример лестницы. Найдите в заданной таблице максимальное количество клеток, образующих лестницу.
Первая строка входных данных содержит два целых числа h и w (1 ⩽ h, w ⩽ 2 · 105 , h · w ⩽ 4 · 106 ) — количество строк и столбцов таблицы соответственно. Каждая из следующих h строк содержит по w символов, каждый из которых равен 0 или 1 — числа, написанные в клетках таблицы. Выведите одно число — максимальное количество клеток, образующих лестницу.
Задача 2. Пересменка в Сириусе
Участники образовательных программ иногда задумываются, почему между двумя программами обычно бывает перерыв в несколько дней. Ответ прост: сотрудникам Сириуса необходимо после очередной программы привести в порядок жилые номера. На одном этаже в гостинице ОЦ «Сириус» находятся n номеров, пронумерованных от 1 до n. После проведения образовательной программы все эти номера нуждаются в ремонте. К ремонтным работам привлечены k сотрудников, пронумерованных от 1 до k. За i-м сотрудником закреплён диапазон номеров с li по ri включительно, а также зафиксирован номер mi из этого диапазона, с которого он должен начать обход своих номеров. Диапазоны номеров у разных сотрудников могут пересекаться и даже совпадать. Сотрудники в некотором порядке направляются с базы для выполнения работ. Следующий сотрудник направляется только после возвращения предыдущего на базу.
Когда i-го сотрудника направляют на выполнение работ, он сначала идёт в номер mi . Если этот номер всё ещё нуждается в ремонте, то сотрудник ремонтирует его, а также посещает все номера из диапазона с li по ri , за который он отвечает, и ремонтирует все нуждающиеся в ремонте номера из этого диапазона, после чего возвращается на базу. После этого все номера из диапазона с li по ri более не нуждаются в ремонте. Если же первый посещённый сотрудником номер mi не нуждается в ремонте, поскольку его уже отремонтировали ранее направленные для выполнения работ коллеги, то сотрудник сразу возвращается на базу, надеясь, что коллеги уже отремонтировали и все остальные номера из его диапазона. В этом случае некоторые другие номера из диапазона с li по ri всё еще могут нуждаться в ремонте. Определите, можно ли при подобном подходе сотрудников к выполнению своих обязанностей направить их всех для выполнения работ в таком порядке, чтобы в итоге все номера от 1 до n оказались отремонтированы.
Формат входных данных
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1 ⩽ t ⩽ 105 ) — количество наборов входных данных. Далее следует описание наборов входных данных. Первая строка каждого набора входных данных содержит два целых числа n и k (1 ⩽ n, k ⩽ 5 · 105 ) — количество номеров и количество сотрудников соответственно. В каждой из последующих k строк содержится три целых числа li , mi и ri (1 ⩽ li ⩽ mi ⩽ ri ⩽ n) — первый номер диапазона ответственности i-го сотрудника, номер из диапазона, с которого он должен начать обход своих, и последний номер из его диапазона, соответственно. Гарантируется, что сумма n и k по всем наборам входных данных не превосходит 5 · 105 . Для каждого набора входных данных в отдельной строке выведите «YES», если можно отремонтировать все номера, и «NO» — в противном случае.
Задача 3. Сочи Парк
В Сочи Парке открылся новый аттракцион. Вдоль прямой расположены n целей, координата i-й цели равна xi (1 ⩽ i ⩽ n). Посетители должны поразить все эти цели в произвольном порядке. Для поражения целей используются мячики. Если посетитель находится в точке с координатой x и хочет поразить цель, находящуюся в точке xi , ему потребуется потратить (x − xi) 2 калорий. Посетитель входит в аттракцион в точке с координатой x0. Неограниченные запасы мячиков находятся в точке входа, а также во всех точках на расстоянии d друг от друга, то есть в точках x0 + kd, где k — произвольное целое число. Переносить мячики запрещено правилами аттракциона, поэтому бросать их можно только из этих точек. В день между турами m участников олимпиады посещают в Сочи Парк. Участники соревнования находятся в разной физической форме, поэтому j-му участнику олимпиады для перемещения на расстояние d требуется tj калорий. Вам нужно определить, какое минимальное число калорий необходимо каждому участнику для поражения всех целей аттракциона.
В первой строке задано одно целое число n (1 ⩽ n ⩽ 3 · 105 ) — количество целей в аттракционе. Во второй строке заданы n целых чисел x1, x2, . . . , xn (0 ⩽ xi ⩽ 109 ) — координаты целей. В третьей строке заданы два целых числа x0 и d (0 ⩽ x0 ⩽ 109 , 1 ⩽ d ⩽ 2 · 106 ) — точка входа посетителя аттракциона и расстояние между местами нахождения запасов мячиков. В четвертой строке задано одно целое число m (1 ⩽ m ⩽ 6 · 105 ) — количество участников олимпиады. В следующих m строках содержится по одному целому числу tj (0 ⩽ tj ⩽ 108 ) — количество энергии, необходимое j-му участнику олимпиады для перемещения между двумя соседними местами нахождения запасов мячиков.
Для каждого участника олимпиады выведите одно целое число — минимальное количество, необходимое ему для перемещения и поражения всех целей. При данных ограничениях ответ не превосходит максимального значения 64-битного знакового типа данных. Однако для промежуточных вычислений может понадобиться тип данных __int128 в C++ (поддерживается только в компиляторе GNU C++), BigInteger в Java, int в Python.
Задача 4. Лягушки на дереве
На ФТ Сириус можно наблюдать не только обыкновенных, но и древесных лягушек, про некоторые виды которых известно, что они могут менять свой цвет с зелёного на коричневый, и наоборот. Как известно, дерево — это связный граф без циклов. В каждой вершине дерева живёт ровно одна лягушка. Изначально все лягушки имеют зелёный цвет. Лягушки могут прыгать по дереву. За один прыжок лягушка перемещается из вершины дерева, в которой она находится, в соседнюю с ней по ребру вершину. После каждого прыжка цвет лягушки меняется на противоположный. Лягушки любят петь дуэтом. Дуэт обязательно должен состоять из двух лягушек разного цвета.
Чтобы две лягушки образовали дуэт, одна из лягушек должна добраться до вершины, где живет другая лягушка, совершив при этом не более d прыжков. Чтобы после перемещения цвет гостьи отличался от цвета хозяйки, гостья должна сделать нечётное количество прыжков. Необходимо определить, какое максимальное количество дуэтов лягушек может образоваться. Каждая лягушка может входить только в один дуэт. Если вы правильно определите максимальное количество дуэтов, вы получите частичный балл за подзадачу. Чтобы получить полный балл за подзадачу необходимо также выяснить, какие пары лягушек должны образовать дуэты, чтобы их оказалось максимальное количество.
Первая строка входных данных содержит одно целое число n (2 ⩽ n ⩽ 5 · 105 ) — количество вершин в дереве. Вторая строка входных данных содержит одно целое нечётное число d (1 ⩽ d ⩽ n − 1) — максимальное количество прыжков, которое может сделать одна лягушка на пути к другой. Каждая из следующих n − 1 строк входных данных содержит два целых числа u и v (1 ⩽ u, v ⩽ n) — номера вершин дерева, соединённых одним ребром. Вершины пронумерованы от 1 до n. В первой строке выведите одно целое число m — максимально возможное количество дуэтов лягушек, которые могут образоваться. Если вы не хотите предъявлять сами пары, то выведите в следующей строке число −1 и завершите работу программы. Иначе, в следующих m строках выведите по два целых числа ui и vi — пару вершин, лягушки из которых должны встретиться в одной из этих вершин и образовать дуэт, соблюдая описанные выше правила. Если максимальное количество дуэтов может быть образовано несколькими способами, выведите любой из них.
Задача 5. Качественный отдых
Прохор проходит стажировку продолжительностью n календарных дней в ИТ-компании. Прохор стажируется в службе поддержки, поэтому у него сложный график рабочих и выходных дней на время стажировки. Кроме выходных, у Прохора есть некоторое количество отгулов — дополнительных выходных дней, которые он может взять в любые рабочие дни. За один выходной день Прохор качественно отдохнуть не сможет, поэтому он считает днями качественного отдыха только те выходные дни, которые входят в последовательность из идущих подряд двух или более выходных дней. Вам даны q запросов — различных значений количества отгулов, которые может взять Прохор. Ваша задача — по заданному графику рабочих и выходных дней стажировки определить для каждого запроса, какое максимальное количество дней качественного отдыха за время стажировки может получить Прохор.
Первая строка входных данных содержит два целых числа n и q (1 6 n 6 100 000, 1 6 q 6 n+ 1). Следующая строка содержит строку s длины n, состоящую из символов «0» и «1» — график стажировки. В этой строке символом «0» обозначается рабочий день, а символом «1» — выходной. В следующих q строках находятся q целых чисел ki (0 6 ki 6 n) — количество отгулов в i-м запросе. Гарантируется, что каждое значение ki не превосходит количества рабочих дней в графике стажировки. Выведите q целых чисел — для каждого значения ki определите наибольшее количество качественных дней отдыха, которое может получить Прохор за время стажировки, выбрав ki дополнительных выходных дней.
Задача 6. Лягушки на болоте
В Сочи при подготовке Олимпиады-2014 была завезена самшитовая огнёвка (небольшая бабочка с Дальнего Востока). Она уничтожила самшитовую рощу, поэтому древесным лягушкам теперь приходится жить на болоте. Но они сохранили способность после прыжка менять свой цвет с зелёного на коричневый и наоборот. Болото представляет собой плоскость, в некоторых точках которой располагаются кочки. Размером кочек можно пренебречь и считать их точками на плоскости. За один прыжок лягушка может перепрыгнуть с кочки, на которой она находится, на любую другую кочку, которая находится от неё на расстоянии не более r. После каждого прыжка цвет лягушки меняется на противоположный. Прыгать на месте лягушка не умеет. Вам необходимо для каждой стартовой кочки лягушки от 1 до n определить, может ли она, совершив некоторое количество прыжков, вернуться на стартовую кочку, поменяв при этом свой цвет.
Первая строка содержит два целых числа n и r (2 6 n 6 105 , 1 6 r 6 109 ) — число кочек на болоте и расстояние, на которое прыгает лягушка. Каждая из следующих n строк описывает расположение кочек. В i-й из них содержатся два целых числа xi и yi (0 6 xi , yi 6 5 · 108 ) — координаты i-й кочки. Никакие две кочки не располагаются в одной точке. Выведите строку, состоящую из n символов. Если лягушка, стартовав с кочки i, может вернуться на неё, имея противоположный цвет, i-й символ должен быть «1», а иначе — «0».
Задача 7. Минимизация инверсий
Дана таблица a, состоящая из r строк и c столбцов, в которой записаны в произвольном порядке все различные числа от 1 до r ·c. Элементы этой таблицы переносятся в изначально пустой массив b. Пока таблица непустая, над ней выполняется одно из двух действий: • Дописать в конец массива элементы первой строки таблицы в порядке от элемента в первом столбце до элемента в последнем и удалить первую строку из таблицы. • Дописать в конец массива элементы первого столбца таблицы в порядке от элемента в первой строке до элемента в последней и удалить первый столбец из таблицы. Порядок действий требуется выбирать таким, чтобы количество инверсий в полученном массиве после применения всех операций было минимальным. Инверсией называется такая пара индексов элементов массива 1 6 i < j 6 r · c, что bi > bj .
Первая строка содержит два целых числа r и c (r 6 c, 1 6 r · c 6 2 000 000) — количество строк и столбцов в таблице соответственно. В следующих r строках содержится описание таблицы a. В i-й из них содержится c целых чисел ai1, . . ., aic (1 6 aij 6 r · c) — элементы матрицы a. Гарантируется, что все числа в таблице a различны. Выведите одно число — минимально возможное количество инверсий в массиве b после применения всех операций.
Задача 8. Жизнь программистов
Новый сериал про жизнь программистов содержит n серий, пронумерованных от 1 до n. Телекомпания Сириус ТВ планирует показывать серии по очереди от первой до последней в течение k дней, каждый день показывая блок из одной или нескольких подряд идущих серий. Каждая серия будет показана ровно один раз. По результатам тестовых просмотров маркетологи компании составили рейтинг серий: i-й серии сопоставлено число ai от 1 до n, самая интересная серия получила рейтинг 1, а самая скучная — рейтинг n. Рейтинги различных серий различны, поэтому числа [a1, a2, . . . , an] образуют перестановку. Пусть принято решение о том, в какой день какие серии будут показаны. Для каждого дня определим рейтинг этого дня, равный рейтингу самой скучной серии этого дня.
Иначе говоря, пусть в j-й день показываются серии с lj по rj , тогда рейтинг этого дня bj равен максимальному значению среди [alj , alj+1, . . . , arj ]. Чтобы показ сериала был удачным, необходимо вовлечь зрителей в просмотр. Среди всех возможных способов разбить серии на k блоков по дням необходимо выбрать тот, в котором рейтинг первого дня как можно лучше: b1 минимально. Среди этих способов в свою очередь необходимо минимизировать рейтинг второго дня b2, при выбранных значениях b1 и b2 — минимизировать b3, и так далее. Таким образом, необходимо разбить показ серий на k блоков таким образом, чтобы лексикографически минимизировать последовательность [b1, b2, . . . , bk]. Вам необходимо ответить на q запросов, каждый из которых задаётся двумя числами: k и i. В качестве ответа на запрос необходимо вывести значение bi — рейтинг i-го дня для оптимального способа показать сериал за k дней.
В первой строке входных данных содержится два целых числа n и q (1 6 n, q 6 300 000) — количество серий и количество запросов соответственно. Во второй строке входных данных содержатся n целых чисел a1, a2, . . . , an (1 6 ai 6 n) — рейтинги серий. Гарантируется, что массив a является перестановкой целых чисел от 1 до n. Следующие q строк содержат по два целых числа k и i (1 6 i 6 k 6 n) — параметры очередного запроса.
Проходные баллы на заключительный этап 2025
Заключительный этап 2025 проходные баллы для 9, 10, 11 класса олимпиады ВСОШ