Олимпиада школьного этапа ВсОШ по Информатике (Программирование) 9-11 класса задания и ответы: 2 группа, 22 октября 2026. Полный доступ к ответам и разбору всероссийской олимпиады, проходящей на площадке uts.sirius.
Скачать полные задания и ответы
Олимпиада ВсОШ по Информатике (Программирование) 9-11 класс 2 группа
Задание 1. Лоуху
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
В древнем Китае для измерения времени использовали водяные часы — лоуху.
В нижнем сосуде часов изначально находится v миллилитров воды.
Каждые a секунд, то есть в моменты времени a, 2a, 3a, …, в сосуд поступает 1 миллилитр воды.
Каждые b секунд, то есть в моменты времени b, 2b, 3b, …, из сосуда вытекает 1 миллилитр воды.
Если поступление и вытекание происходят одновременно, объём воды в этот момент не изменяется.
Определите, сколько миллилитров воды будет в сосуде через n секунд. События, происходящие ровно в момент n, также должны быть учтены.
Гарантируется, что воды в сосуде достаточно для всех вытеканий до момента n, даже если не учитывать поступления новой воды.
Формат входных данных
В единственной строке даны четыре целых числа v, a, b и n (0 ≤ v ≤ 10^18, 1 ≤ a, b ≤ 10^18, 0 ≤ n ≤ 10^18).
Формат выходных данных
Выведите одно целое число — объём воды в сосуде через n секунд.
Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при a = b, будут оцениваться в 10 баллов.
Решения, правильно работающие при b = 1, будут оцениваться в 10 баллов.
Решения, правильно работающие при n ≤ 1000, будут оцениваться в 50 баллов.
Решения, правильно работающие при не более 10^6 поступлений и вытеканий суммарно за первые n секунд, будут оцениваться в 70 баллов.
Пример 1.
Ввод:
10
3
5
14
Вывод:
12
Пример 2.
Ввод:
20
4
6
12
Вывод:
21
Пример 3.
Ввод:
7
2
3
0
Вывод:
7
→Узнать ответ
Задание 2. Доставка
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Склад службы доставки находится в точке 0 на прямой дороге. Два посёлка находятся в точках x и y. Положительные и отрицательные координаты соответствуют разным направлениям от склада. Все координаты измеряются в километрах, расстояние между точками с координатами u и v равно |u − v|.
В посёлок с координатой x нужно доставить контейнер массой a, а в посёлок с координатой y — контейнер массой b.
Для доставки используется дрон. За один рейс он может перевезти груз суммарной массой не более m килограммов и пролететь не более d километров. Каждый рейс начинается и заканчивается на складе. Все контейнеры, доставляемые за один рейс, загружаются в дрон перед вылетом. Во время рейса дрон не может брать на складе дополнительные контейнеры или заряжаться, даже если его маршрут снова проходит через склад. Перед новым рейсом дрон полностью заряжается.
За один рейс дрон может доставить один контейнер или оба контейнера, посетив посёлки в любом порядке.
Определите минимальное количество рейсов, необходимое для доставки обоих контейнеров. Если выполнить доставку невозможно, выведите −1.
Формат входных данных
В первой строке записано целое число x (−5 · 10^8 ≤ x ≤ 5 · 10^8, x ≠ 0) — координата первого посёлка.
Во второй строке записано целое число y (−5 · 10^8 ≤ y ≤ 5 · 10^8, y ≠ 0, y ≠ x) — координата второго посёлка.
В третьей строке записано целое число a (1 ≤ a ≤ 10^9) — масса контейнера для первого посёлка.
В четвёртой строке записано целое число b (1 ≤ b ≤ 10^9) — масса контейнера для второго посёлка.
В пятой строке записано целое число m (1 ≤ m ≤ 10^9) — грузоподъёмность дрона.
В шестой строке записано целое число d (1 ≤ d ≤ 2 · 10^9) — максимальное расстояние, которое дрон может пролететь за один рейс.
Формат выходных данных
Выведите одно целое число — минимальное количество рейсов, необходимое для доставки обоих контейнеров, или −1, если доставка невозможна.
Замечание
В первом примере каждый контейнер можно доставить отдельным рейсом. Если же попытаться доставить оба контейнера за один рейс, дрону придётся пролететь 4 + 10 + 6 = 20 километров, что превышает допустимое расстояние. Поэтому требуется два рейса.
Во втором примере дрон может поднять оба контейнера. Он пролетит от склада до первого посёлка 3 километра, затем до второго посёлка ещё 5 километров и вернётся на склад, преодолев ещё 8 километров. Общая длина маршрута равна 16 километрам, поэтому достаточно одного рейса.
В третьем примере масса первого контейнера превышает грузоподъёмность дрона, поэтому выполнить доставку невозможно.
Пример 1.
Ввод:
-4
6
2
3
10
16
Вывод:
2
Пример 2.
Ввод:
3
8
4
5
9
16
Вывод:
1
Пример 3.
Ввод:
2
7
6
3
5
20
Вывод:
-1
→Узнать ответ
Задание 3. Клумба
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Садовник хочет разбить прямоугольную клумбу и огородить её по периметру. Для клумбы он может выделить не более s квадратных метров земли и использовать не более p метров ограждения. Длины сторон клумбы a и b, измеренные в метрах, должны быть натуральными числами. Поэтому выбранный размер клумбы подходит, если одновременно выполняются условия ab ≤ s, 2(a + b) ≤ p.
Два размера считаются одинаковыми, если соответствующие клумбы совпадают после поворота.
В частности, размеры a × b и b × a считаются одинаковыми.
Сколько существует различных размеров подходящей клумбы?
Формат входных данных
В первой строке записано целое число s (1 ≤ s ≤ 10^12) — максимальная доступная площадь земли.
Во второй строке записано целое число p (4 ≤ p ≤ 10^12) — максимальная доступная длина ограждения.
Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Выведите одно целое число — количество различных размеров подходящей клумбы.
Система оценки
Решения, правильно работающие при s ≤ 2000, p ≤ 2000 или в случаях, когда земли достаточно для любой клумбы, которую можно огородить имеющимся ограждением, получат не менее 15 баллов.
Решения, правильно работающие в случаях, когда ограждения достаточно для любой клумбы площадью не более s, получат не менее 20 баллов.
Решения, правильно работающие при p ≤ 2 · 10^6, получат не менее 35 баллов. Если они также работают во всех случаях, когда земли достаточно, они получат не менее 50 баллов; когда ограждения достаточно — не менее 55 баллов; когда соблюдаются оба условия — не менее 70 баллов.
Замечание
В первом примере для стороны a = 1 подходят семь значений стороны b от 1 до 7, для a = 2 — пять значений от 2 до 6, а для a = 3 — два значения: 3 и 4. Всего существует 7 + 5 + 2 = 14 различных размеров клумбы.
Во втором примере подходит только квадрат со стороной 1.
Пример 1.
Ввод:
12
16
Вывод:
14
Пример 2.
Ввод:
1
4
Вывод:
1
→Узнать ответ
Задание 4. Саунд-чек
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Рок-группа готовится к грандиозному концерту. На сцене в один ряд установлено N звуковых мониторов. Изначально громкость i-го монитора равна a_i. Для удобства настройки мониторы уже упорядочены по неубыванию громкости: a_1 ≤ a_2 ≤ … ≤ a_N. Количество мониторов N чётно.
Звукорежиссёр хочет избавиться от «глухих» зон на сцене. Его цель — сделать так, чтобы минимальная громкость среди всех мониторов стала как можно большей (то есть максимизировать величину min(a_1, a_2, …, a_N)).
Для настройки звука используется специальный микшерный пульт. За одно действие звукорежиссёр может выбрать любой подотрезок из ровно N/2 подряд идущих мониторов и увеличить громкость каждого из них на 1. До выхода музыкантов осталось совсем немного времени, поэтому звукорежиссёр успеет выполнить не более K таких действий.
Помогите звукорежиссёру определить максимально возможное значение минимальной громкости среди всех мониторов, доступное после выполнения не более K операций.
Формат входных данных
В первой строке входных данных записано целое число N — количество звуковых мониторов.
Во второй строке записано целое число K — максимальное число действий звукорежиссёра.
Числа N и K удовлетворяют условиям (2 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^9).
Гарантируется, что N — чётное число.
В следующих N строчках заданы целые числа a_1, a_2, …, a_N по одному в каждой строке — изначальные уровни громкости мониторов (1 ≤ a_i ≤ 10^9).
Гарантируется, что a_1 ≤ a_2 ≤ … ≤ a_N.
Формат выходных данных
Выведите одно целое число — максимально возможное значение min(a_1, a_2, …, a_N), которого можно достичь, выполнив не более K операций.
Система оценки
Решения, правильно работающие при n = 2, будут оцениваться не менее чем в 24 балла.
Решения, правильно работающие при k = 1, будут оцениваться не менее чем в 16 баллов.
Решения, правильно работающие при n ≤ 2000 и k ≤ 2000, будут оцениваться не менее чем в 48 баллов.
Решения, правильно работающие при n ≤ 2000, будут оцениваться не менее чем в 68 баллов.
Замечание
Пояснение к первому примеру.
Изначально уровни громкости мониторов равны [1, 2, 4, 5]. Длина подотрезка, на котором можно увеличивать громкость, равна N/2 = 2. Звукорежиссёр может выполнить три действия.
Один из оптимальных способов достичь ответа 4:
1. Увеличить громкость на подотрезке из первых двух мониторов: массив станет [2, 3, 4, 5].
2. Снова выбрать первые два монитора: массив станет [3, 4, 4, 5].
3. И в третий раз применить пульт к первым двум мониторам: массив станет [4, 5, 4, 5].
Минимальный уровень громкости равен 4. Сделать его больше невозможно.
Пояснение ко второму примеру.
Изначально массив равен [2, 2, 3, 5, 7, 8]. Длина подотрезка равна 3, доступно пять действий.
Один из оптимальных способов достичь ответа 6:
1. Применим пульт три раза подряд к подотрезку из первых трёх мониторов. Массив станет [5, 5, 6, 5, 7, 8].
2. Четвёртое действие снова применим к первым трём мониторам. Массив станет [6, 6, 7, 5, 7, 8].
3. Пятое действие применим к последним трём мониторам. Массив станет [6, 6, 7, 6, 8, 9].
Минимальный уровень громкости равен 6.
Пример 1.
Ввод:
4
3
1
2
4
5
Вывод:
4
Пример 2.
Ввод:
6
5
2
2
3
5
7
8
Вывод:
6
→Узнать ответ
Задание 5. Особенная бусина
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
У Алисы есть нитка бус, состоящая из N бусин. Каждая бусина имеет свой цвет, который задаётся целым числом от 1 до M.
Алисе очень нравится цвет X. Она хочет вырезать из нитки непрерывный фрагмент (подотрезок) так, чтобы в нём бусина её любимого цвета X встречалась ровно один раз. Это позволит ей сделать красивый браслет с единственным ярким акцентом.
Помогите Алисе посчитать, сколько существует различных способов выбрать такой непрерывный фрагмент. Два фрагмента считаются различными, если они отличаются начальной или конечной позицией в исходной нитке бус.
Формат входных данных
В первой строке задано целое число N (1 ≤ N ≤ 2 · 10^5) — количество бусин на нитке.
Во второй строке задано целое число M (1 ≤ M ≤ 2 · 10^5) — количество возможных цветов.
В третьей строке задано целое число X (1 ≤ X ≤ M) — любимый цвет Алисы.
В каждой из следующих N строк задано по одному целому числу A_i (1 ≤ A_i ≤ M) — цвет i-й бусины на нитке, считая слева направо.
Формат выходных данных
Выведите одно целое число — количество непрерывных подотрезков, на которых бусина цвета X встречается ровно один раз.
Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при N ≤ 100, будут оцениваться в 15 баллов.
Решения, правильно работающие при N ≤ 2000, будут оцениваться в 40 баллов.
Решения, правильно работающие, когда бусинка цвета X в массиве ровно одна, будут оцениваться в 10 баллов.
Замечание
Пояснение к первому примеру.
В массиве из 5 бусин нас интересуют подотрезки, где бусина любимого цвета 2 встречается ровно один раз.
Подходящие подотрезки (в 1-индексации):
• [1, 2]: цвета 1, 2;
• [1, 3]: цвета 1, 2, 3;
• [2, 2]: цвет 2;
• [2, 3]: цвета 2, 3;
• [3, 4]: цвета 3, 2;
• [3, 5]: цвета 3, 2, 1;
• [4, 4]: цвет 2;
• [4, 5]: цвета 2, 1.
Итого существует 8 таких фрагментов.
Отрезок [1, 5] не подходит, так как на нём бусина цвета 2 встречается дважды. Отрезок [1, 1] не подходит, так как на нём вообще нет цвета 2.
Пояснение ко второму примеру.
Любимый цвет Алисы (1) вообще не встречается на нитке бус. Следовательно, невозможно вырезать ни одного подходящего фрагмента. Ответ — 0.
Пример 1.
Ввод:
5
3
2
1
2
3
2
1
Вывод:
8
Пример 2.
Ввод:
4
5
1
2
3
4
5
Вывод:
0
→Узнать ответ
