Ответы и авторские решения на все задания для 5-6, 7-8, 9-11 класса онлайн олимпиада по программированию информатика 22 октября 2026 школьный этап ВСОШ официальной всероссийской олимпиады школьников 2 группы регионов Сириус всего в олимпиаде 6 заданий от Академии сова приступить к прохождению не позднее 19:00 22 октября 2026 года.
Олимпиада по программированию 5-6 класс школьный этап 2026
1. Буквы в коробках
Даны пять коробок, пронумерованных от 1 до 5. В каждой из них лежит карточка с одной буквой из пяти: А, Б, В, Г, Д.
За один ход можно поменять местами содержимое двух любых коробок. Например, запись 13 означает: «взять листок из 1-й коробки и поменять его с листком из 3-й».
Составьте последовательность таких операций, чтобы в итоге буквы в коробках располагались в алфавитном порядке: в первой коробке — А, во второй — Б, в третьей — В, в четвёртой — Г, а в пятой — Д.
Чем меньше операций вам потребуется, тем больше баллов вы получите.
Рассмотрим пример. Пусть у нас всего три коробки, и буквы в них лежат в таком порядке: В, А, Б.
Чтобы расставить их по алфавиту (А, Б, В), можно сделать два действия:
1) Сначала меняем местами 1-ю и 2-ю коробки (12). Получится А, В, Б.
2) Затем меняем местами 2-ю и 3-ю коробки (23). Получится А, Б, В.
Ответ для этого примера: 12 23
Ответ: 14 25 34
2. Школьная фотография
Аня, Боря, Вера, Глеб, Даша и Егор встали в один ряд для школьной фотографии. Фотограф сделал первый снимок.
Затем один из школьников, который стоял не первым слева, вышел из ряда и встал на левый край, перед всеми остальными. Остальные сохранили свой взаимный порядок. Фотограф сделал второй снимок.
Снимки потерялись, но помощник фотографа запомнил несколько подробностей. На первом снимке:
- между Аней и Глебом стоял ровно один человек;
- Аня стояла левее Глеба;
- Даша стояла с краю.
На втором снимке:
- Боря и Егор стояли рядом;
- Боря и Даша стояли рядом;
- Даша стояла левее Егора;
- Вера и Егор стояли рядом.
Все воспоминания помощника верны. Слово «рядом» означает, что между ребятами никто не стоял; «с краю» — на первом или последнем месте. Лево и право определяются с точки зрения фотографа.
В каком порядке слева направо стояли ребята на первом снимке?
В каком порядке слева направо стояли ребята на втором снимке?
Кто перешёл на левый край?
А) Аня; Б) Боря; В) Вера; Г) Глеб; Д) Даша; Е) Егор.
Ответ: первый снимок — Даша, Боря, Егор, Аня, Вера, Глеб; второй снимок — Аня, Даша, Боря, Егор, Вера, Глеб; на левый край перешла Аня
3. Сжатие текста
Глеб придумал способ короче записывать строки из букв. Если один и тот же фрагмент повторяется несколько раз подряд, его можно записать один раз в скобках, а перед скобками указать количество повторений. Например, запись 4(аб) означает абабабаб, а запись 6(а)б — ааааааб. В одной записи можно использовать несколько таких блоков и обычные буквы. Запись читается слева направо: обычные буквы переписываются без изменений, а каждый блок заменяется указанным количеством копий фрагмента. В результате должна получиться в точности исходная строка.
Внутри скобок записывается одна или несколько букв. Скобки внутри скобок использовать нельзя. Количество повторений не может быть меньше 2.
Длина записи — количество всех её символов без пробелов. Каждая буква, каждая цифра и каждая скобка считаются за один символ. Например, длина записи 6(а)б равна 5.
Запишите каждую из следующих строк как можно короче.
1) аааааааа
2) абабабабаб
3) абабабвабабабв
4) аааааааабааааааааб
5) абабабабабвабвабвабв
Ответ: 1) 8(а); 2) 5(аб); 3) 2(абабабв); 4) 8(а)б8(а)б; 5) 4(аб)4(абв)
4. Японские кроссворды
Глеб составляет японские кроссворды по чёрно-белым рисункам на клетчатой бумаге. Для этого он использует сканер, который записывает числовые подсказки для всех строк и столбцов рисунка.
Сканер рассматривает каждую строку отдельно. Все чёрные клетки, идущие подряд, образуют одну группу. Группа заканчивается перед белой клеткой или на краю строки. Для каждой группы сканер записывает количество клеток в ней. Эти числа перечисляются слева направо. Отдельной чёрной клетке соответствует число 1. Столбцы обрабатываются таким же образом, но сверху вниз. Количество белых клеток между группами и по краям рисунка не записывается.
На рисунке показан узор размером 6 × 6 и записи сканера: числа слева относятся к строкам, а числа сверху — к столбцам.
Например, в четвёртой строке сначала стоит одна чёрная клетка, а затем, после белой клетки, ещё две чёрные клетки подряд. Поэтому слева записаны числа 1, 2. В пятом столбце три чёрные клетки идут подряд, поэтому сверху стоит число 3.
Сканер запоминает длины и порядок чёрных групп, но не записывает количество белых клеток до, после и между ними.
Помогите обмануть сканер: перекрасьте некоторые клетки так, чтобы получился другой рисунок, но списки чисел во всех строках и во всех столбцах остались прежними. Каждая строка и каждый столбец должны сохранить именно свой список, включая порядок чисел. Постарайтесь изменить как можно меньше клеток.
Каждую клетку можно перекрасить с белой на чёрную или с чёрной на белую. Число изменений — количество клеток, цвета которых в итоговом рисунке отличаются от исходных. Порядок перекрашивания не учитывается.
Отметьте клетки, которые необходимо перекрасить.
5. Сигнальная панель
На панели расположены 8 ламп, пронумерованных слева направо от 1 до 8. Для каждого сигнала от A до G в таблице указано состояние исправной панели. Оно записывается строкой из восьми нулей и единиц: i-й символ слева соответствует лампе с номером i; 1 означает, что она горит, а 0 — что не горит. После ремонта провода двух ламп перепутали местами: каждая получает команду, предназначенную для другой. Ещё одна лампа работает наоборот: горит, когда должна быть выключена, и не горит, когда должна быть включена. Эти три лампы различны, остальные исправны. Характер поломок не меняется при переключении сигналов.
| Сигнал | Состояние |
|---|---|
| A | 01110100 |
| B | 10100101 |
| C | 11010001 |
| D | 10110100 |
| E | 11100010 |
| F | 00011011 |
| G | 11001001 |
При сигнале A панель показала 00111110. Сколькими способами можно выбрать пару ламп с перепутанными проводами и третью лампу, работающую наоборот, чтобы получилось это состояние? Порядок ламп в паре не учитывается.
Какие сигналы не позволят различить варианты из предыдущего вопроса?
B, C, D, E, F, G.
При том же расположении неисправностей дополнительно проверили сигнал E. Панель показала 11101010.
Определите номера двух ламп с перепутанными проводами: _____ и _____.
Определите номер лампы, работающей наоборот: _____.
Олимпиада по программированию 7-8 класс школьный этап 2026
1. Панорама
У фотографа на карте памяти осталось место для n снимков. Он хочет использовать всю оставшуюся память, чтобы сфотографировать участок стены длиной d сантиметров и объединить снимки в панораму. Каждый снимок охватывает участок стены длиной k сантиметров. Фотограф делает ровно n снимков слева направо: каждый следующий снимок смещён вправо относительно предыдущего. Все соседние снимки должны перекрываться на одинаковую ширину. Первый снимок начинается у левого края участка, а последний заканчивается у правого края. Снимки не должны выходить за границы участка.
Запишите формулу, которая по значениям n, k и d вычисляет ширину пересечения соседних снимков в сантиметрах. Ширина пересечения может быть дробной.
Величины n, k и d являются целыми числами. Гарантируется, что n ⩾ 2, k > 0 и k < d < n · k. Ваше выражение должно давать правильный ответ для любых значений, удовлетворяющих этим условиям.
Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменные n, k и d (обозначаются строчными английскими буквами), операции сложения (обозначаются +), вычитания (обозначаются −), умножения (обозначаются *), деления (обозначаются /) и круглые скобки. Запись вида 2k для обозначения произведения числа 2 и переменной k некорректна, нужно писать 2 * k.
Ваше выражение должно давать правильный ответ для любых допустимых значений n, k и d.
Пример правильной формы записи ответа:
(n + k)/2 + d
Приведённая формула показывает только допустимую форму записи и не является правильным ответом на задачу.
Ответ: (n * k — d)/(n — 1)
2. Сигнальная панель
На панели расположены 8 ламп, пронумерованных слева направо от 1 до 8. Для каждого сигнала от A до G в таблице указано состояние исправной панели. Оно записывается строкой из восьми нулей и единиц: i-й символ слева соответствует лампе с номером i; 1 означает, что она горит, а 0 — что не горит. После ремонта провода двух ламп перепутали местами: каждая получает команду, предназначенную для другой. Ещё одна лампа работает наоборот: горит, когда должна быть выключена, и не горит, когда должна быть включена. Эти три лампы различны, остальные исправны. Характер поломок не меняется при переключении сигналов.
| Сигнал | Состояние |
|---|---|
| A | 01110100 |
| B | 10100101 |
| C | 11010001 |
| D | 10110100 |
| E | 11100010 |
| F | 00011011 |
| G | 11001001 |
При сигнале A панель показала 00111110. Сколькими способами можно выбрать пару ламп с перепутанными проводами и третью лампу, работающую наоборот, чтобы получилось это состояние? Порядок ламп в паре не учитывается.
Какие сигналы не позволят различить варианты из предыдущего вопроса?
B, C, D, E, F, G.
При том же расположении неисправностей дополнительно проверили сигнал E. Панель показала 11101010.
Определите номера двух ламп с перепутанными проводами: _____ и _____.
Определите номер лампы, работающей наоборот: _____.
Ответ: количество способов — 2; не позволяют различить варианты сигналы C и F; перепутаны провода ламп 2 и 7; наоборот работает лампа 5
3. Сигналы
Файл: data.csv
Астрономы получили набор радиосигналов из одного участка неба. Для каждого сигнала удалось определить его частоту.
Для подсчёта различных источников сигналы располагают в порядке возрастания частоты. Соседние в этом ряду сигналы считают принадлежащими одному источнику, если разность их частот не превосходит k. Если разность больше k, то между этими сигналами проходит граница между двумя источниками. При этом разность между наименьшей и наибольшей частотами одного источника может быть больше k.
Например, при k = 5 сигналы с частотами 101, 103, 108, 120, 122, 125 относятся к двум источникам: первому принадлежат сигналы 101, 103, 108, а второму — 120, 122, 125.
Данные содержатся в файле, который вы можете скачать в формате электронной таблицы Libre Office Calc, Microsoft Excel или CSV.
В таблице в столбце A записаны частоты. Строки таблицы расположены в произвольном порядке.
Помогите астрономам ответить на вопросы. Если вы не знаете ответ, запишите вместо него любое число.
1) Чему равна разность между наибольшей и наименьшей частотами зарегистрированных сигналов?
2) Чему равна наибольшая разность частот двух соседних сигналов после расположения всех сигналов в порядке возрастания частоты?
3) Сколько различных источников было обнаружено при k = 5?
4) Предположим, что значение k изменяется. Какое наименьшее целое значение k нужно выбрать, чтобы все зарегистрированные сигналы относились не более чем к десяти различным источникам?
5) Пусть k = 10. Какое наибольшее количество сигналов было получено от одного источника?
Ответ: 1) 3739; 2) 61; 3) 56; 4) 30; 5) 71
4. Лоуху
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
В древнем Китае для измерения времени использовали водяные часы — лоуху.
В нижнем сосуде часов изначально находится v миллилитров воды.
Каждые a секунд, то есть в моменты времени a, 2a, 3a, …, в сосуд поступает 1 миллилитр воды.
Каждые b секунд, то есть в моменты времени b, 2b, 3b, …, из сосуда вытекает 1 миллилитр воды.
Если поступление и вытекание происходят одновременно, объём воды в этот момент не изменяется.
Определите, сколько миллилитров воды будет в сосуде через n секунд. События, происходящие ровно в момент n, также должны быть учтены.
Гарантируется, что воды в сосуде достаточно для всех вытеканий до момента n, даже если не учитывать поступления новой воды.
Формат входных данных
В единственной строке даны четыре целых числа v, a, b и n (0 ⩽ v ⩽ 1018, 1 ⩽ a, b ⩽ 1018, 0 ⩽ n ⩽ 1018).
Формат выходных данных
Выведите одно целое число — объём воды в сосуде через n секунд.
Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при a = b, будут оцениваться в 10 баллов.
Решения, правильно работающие при b = 1, будут оцениваться в 10 баллов.
Решения, правильно работающие при n ⩽ 1000, будут оцениваться в 50 баллов.
Решения, правильно работающие при не более 106 поступлений и вытеканий суммарно за первые n секунд, будут оцениваться в 70 баллов.
Пример 1 ввода:
10
3
5
14
Пример 1 вывода:
12
Пример 2 ввода:
20
4
6
12
Пример 2 вывода:
21
Пример 3 ввода:
7
2
3
0
Пример 3 вывода:
7
5. Доставка
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Склад службы доставки находится в точке 0 на прямой дороге. Два посёлка находятся в точках x и y. Положительные и отрицательные координаты соответствуют разным направлениям от склада. Все координаты измеряются в километрах, расстояние между точками с координатами u и v равно |u − v|.
В посёлок с координатой x нужно доставить контейнер массой a, а в посёлок с координатой y — контейнер массой b.
Для доставки используется дрон. За один рейс он может перевезти груз суммарной массой не более m килограммов и пролететь не более d километров. Каждый рейс начинается и заканчивается на складе. Все контейнеры, доставляемые за один рейс, загружаются в дрон перед вылетом. Во время рейса дрон не может брать на складе дополнительные контейнеры или заряжаться, даже если его маршрут снова проходит через склад. Перед новым рейсом дрон полностью заряжается.
За один рейс дрон может доставить один контейнер или оба контейнера, посетив посёлки в любом порядке.
Определите минимальное количество рейсов, необходимое для доставки обоих контейнеров. Если выполнить доставку невозможно, выведите −1.
Формат входных данных
В первой строке записано целое число x (−5 · 108 ⩽ x ⩽ 5 · 108, x ≠ 0) — координата первого посёлка.
Во второй строке записано целое число y (−5 · 108 ⩽ y ⩽ 5 · 108, y ≠ 0, y ≠ x) — координата второго посёлка.
В третьей строке записано целое число a (1 ⩽ a ⩽ 109) — масса контейнера для первого посёлка.
В четвёртой строке записано целое число b (1 ⩽ b ⩽ 109) — масса контейнера для второго посёлка.
В пятой строке записано целое число m (1 ⩽ m ⩽ 109) — грузоподъёмность дрона.
В шестой строке записано целое число d (1 ⩽ d ⩽ 2 · 109) — максимальное расстояние, которое дрон может пролететь за один рейс.
Формат выходных данных
Выведите одно целое число — минимальное количество рейсов, необходимое для доставки обоих контейнеров, или −1, если доставка невозможна.
Замечание
В первом примере каждый контейнер можно доставить отдельным рейсом. Если же попытаться доставить оба контейнера за один рейс, дрону придётся пролететь 4 + 10 + 6 = 20 километров, что превышает допустимое расстояние. Поэтому требуется два рейса.
Во втором примере дрон может поднять оба контейнера. Он пролетит от склада до первого посёлка 3 километра, затем до второго посёлка ещё 5 километров и вернётся на склад, преодолев ещё 8 километров. Общая длина маршрута равна 16 километрам, поэтому достаточно одного рейса.
В третьем примере масса первого контейнера превышает грузоподъёмность дрона, поэтому выполнить доставку невозможно.
Пример 1 ввода:
-4
6
2
3
10
16
Пример 1 вывода:
2
Пример 2 ввода:
3
8
4
5
9
16
Пример 2 вывода:
1
Пример 3 ввода:
2
7
6
3
5
20
Пример 3 вывода:
-1
6. Клумба
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Садовник хочет разбить прямоугольную клумбу и огородить её по периметру. Для клумбы он может выделить не более s квадратных метров земли и использовать не более p метров ограждения. Длины сторон клумбы a и b, измеренные в метрах, должны быть натуральными числами. Поэтому выбранный размер клумбы подходит, если одновременно выполняются условия ab ⩽ s, 2(a + b) ⩽ p.
Два размера считаются одинаковыми, если соответствующие клумбы совпадают после поворота.
В частности, размеры a × b и b × a считаются одинаковыми.
Сколько существует различных размеров подходящей клумбы?
Формат входных данных
В первой строке записано целое число s (1 ⩽ s ⩽ 1012) — максимальная доступная площадь земли.
Во второй строке записано целое число p (4 ⩽ p ⩽ 1012) — максимальная доступная длина ограждения.
Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Выведите одно целое число — количество различных размеров подходящей клумбы.
Система оценки
Решения, правильно работающие при s ⩽ 2000, p ⩽ 2000 или в случаях, когда земли достаточно для любой клумбы, которую можно огородить имеющимся ограждением, получат не менее 15 баллов.
Решения, правильно работающие в случаях, когда ограждения достаточно для любой клумбы площадью не более s, получат не менее 20 баллов.
Решения, правильно работающие при p ⩽ 2 · 106, получат не менее 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
Пример 1 вывода:
14
Пример 2 ввода:
1
4
Пример 2 вывода:
1
Олимпиада по программированию 9-11 класс школьный этап 2026
1. Лоуху
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
В древнем Китае для измерения времени использовали водяные часы — лоуху.
В нижнем сосуде часов изначально находится v миллилитров воды.
Каждые a секунд, то есть в моменты времени a, 2a, 3a, …, в сосуд поступает 1 миллилитр воды.
Каждые b секунд, то есть в моменты времени b, 2b, 3b, …, из сосуда вытекает 1 миллилитр воды.
Если поступление и вытекание происходят одновременно, объём воды в этот момент не изменяется.
Определите, сколько миллилитров воды будет в сосуде через n секунд. События, происходящие ровно в момент n, также должны быть учтены.
Гарантируется, что воды в сосуде достаточно для всех вытеканий до момента n, даже если не учитывать поступления новой воды.
Формат входных данных
В единственной строке даны четыре целых числа v, a, b и n (0 ⩽ v ⩽ 1018, 1 ⩽ a, b ⩽ 1018, 0 ⩽ n ⩽ 1018).
Формат выходных данных
Выведите одно целое число — объём воды в сосуде через n секунд.
Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при a = b, будут оцениваться в 10 баллов.
Решения, правильно работающие при b = 1, будут оцениваться в 10 баллов.
Решения, правильно работающие при n ⩽ 1000, будут оцениваться в 50 баллов.
Решения, правильно работающие при не более 106 поступлений и вытеканий суммарно за первые n секунд, будут оцениваться в 70 баллов.
Пример 1 ввода:
10
3
5
14
Пример 1 вывода:
12
Пример 2 ввода:
20
4
6
12
Пример 2 вывода:
21
Пример 3 ввода:
7
2
3
0
Пример 3 вывода:
7
Ответ:
2. Доставка
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Склад службы доставки находится в точке 0 на прямой дороге. Два посёлка находятся в точках x и y. Положительные и отрицательные координаты соответствуют разным направлениям от склада. Все координаты измеряются в километрах, расстояние между точками с координатами u и v равно |u − v|.
В посёлок с координатой x нужно доставить контейнер массой a, а в посёлок с координатой y — контейнер массой b.
Для доставки используется дрон. За один рейс он может перевезти груз суммарной массой не более m килограммов и пролететь не более d километров. Каждый рейс начинается и заканчивается на складе. Все контейнеры, доставляемые за один рейс, загружаются в дрон перед вылетом. Во время рейса дрон не может брать на складе дополнительные контейнеры или заряжаться, даже если его маршрут снова проходит через склад. Перед новым рейсом дрон полностью заряжается.
За один рейс дрон может доставить один контейнер или оба контейнера, посетив посёлки в любом порядке.
Определите минимальное количество рейсов, необходимое для доставки обоих контейнеров. Если выполнить доставку невозможно, выведите −1.
Формат входных данных
В первой строке записано целое число x (−5 · 108 ⩽ x ⩽ 5 · 108, x ≠ 0) — координата первого посёлка.
Во второй строке записано целое число y (−5 · 108 ⩽ y ⩽ 5 · 108, y ≠ 0, y ≠ x) — координата второго посёлка.
В третьей строке записано целое число a (1 ⩽ a ⩽ 109) — масса контейнера для первого посёлка.
В четвёртой строке записано целое число b (1 ⩽ b ⩽ 109) — масса контейнера для второго посёлка.
В пятой строке записано целое число m (1 ⩽ m ⩽ 109) — грузоподъёмность дрона.
В шестой строке записано целое число d (1 ⩽ d ⩽ 2 · 109) — максимальное расстояние, которое дрон может пролететь за один рейс.
Формат выходных данных
Выведите одно целое число — минимальное количество рейсов, необходимое для доставки обоих контейнеров, или −1, если доставка невозможна.
Замечание
В первом примере каждый контейнер можно доставить отдельным рейсом. Если же попытаться доставить оба контейнера за один рейс, дрону придётся пролететь 4 + 10 + 6 = 20 километров, что превышает допустимое расстояние. Поэтому требуется два рейса.
Во втором примере дрон может поднять оба контейнера. Он пролетит от склада до первого посёлка 3 километра, затем до второго посёлка ещё 5 километров и вернётся на склад, преодолев ещё 8 километров. Общая длина маршрута равна 16 километрам, поэтому достаточно одного рейса.
В третьем примере масса первого контейнера превышает грузоподъёмность дрона, поэтому выполнить доставку невозможно.
Пример 1 ввода:
-4
6
2
3
10
16
Пример 1 вывода:
2
Пример 2 ввода:
3
8
4
5
9
16
Пример 2 вывода:
1
Пример 3 ввода:
2
7
6
3
5
20
Пример 3 вывода:
-1
Ответ:
3. Клумба
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Садовник хочет разбить прямоугольную клумбу и огородить её по периметру. Для клумбы он может выделить не более s квадратных метров земли и использовать не более p метров ограждения. Длины сторон клумбы a и b, измеренные в метрах, должны быть натуральными числами. Поэтому выбранный размер клумбы подходит, если одновременно выполняются условия ab ⩽ s, 2(a + b) ⩽ p.
Два размера считаются одинаковыми, если соответствующие клумбы совпадают после поворота.
В частности, размеры a × b и b × a считаются одинаковыми.
Сколько существует различных размеров подходящей клумбы?
Формат входных данных
В первой строке записано целое число s (1 ⩽ s ⩽ 1012) — максимальная доступная площадь земли.
Во второй строке записано целое число p (4 ⩽ p ⩽ 1012) — максимальная доступная длина ограждения.
Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Выведите одно целое число — количество различных размеров подходящей клумбы.
Система оценки
Решения, правильно работающие при s ⩽ 2000, p ⩽ 2000 или в случаях, когда земли достаточно для любой клумбы, которую можно огородить имеющимся ограждением, получат не менее 15 баллов.
Решения, правильно работающие в случаях, когда ограждения достаточно для любой клумбы площадью не более s, получат не менее 20 баллов.
Решения, правильно работающие при p ⩽ 2 · 106, получат не менее 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
Пример 1 вывода:
14
Пример 2 ввода:
1
4
Пример 2 вывода:
1
Ответ:
4. Саунд-чек
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Рок-группа готовится к грандиозному концерту. На сцене в один ряд установлено N звуковых мониторов. Изначально громкость i-го монитора равна ai. Для удобства настройки мониторы уже упорядочены по неубыванию громкости: a1 ⩽ a2 ⩽ … ⩽ aN. Количество мониторов N чётно.
Звукорежиссёр хочет избавиться от «глухих» зон на сцене. Его цель — сделать так, чтобы минимальная громкость среди всех мониторов стала как можно большей (то есть максимизировать величину min(a1, a2, …, aN)).
Для настройки звука используется специальный микшерный пульт. За одно действие звукорежиссёр может выбрать любой подотрезок из ровно N/2 подряд идущих мониторов и увеличить громкость каждого из них на 1. До выхода музыкантов осталось совсем немного времени, поэтому звукорежиссёр успеет выполнить не более K таких действий.
Помогите звукорежиссёру определить максимально возможное значение минимальной громкости среди всех мониторов, доступное после выполнения не более K операций.
Формат входных данных
В первой строке входных данных записано целое число N — количество звуковых мониторов.
Во второй строке записано целое число K — максимальное число действий звукорежиссёра.
Числа N и K удовлетворяют условиям (2 ⩽ N ⩽ 105, 1 ⩽ K ⩽ 109).
Гарантируется, что N — чётное число.
В следующих N строчках заданы целые числа a1, a2, …, aN по одному в каждой строке — изначальные уровни громкости мониторов (1 ⩽ ai ⩽ 109).
Гарантируется, что a1 ⩽ a2 ⩽ … ⩽ aN.
Формат выходных данных
Выведите одно целое число — максимально возможное значение min(a1, a2, …, aN), которого можно достичь, выполнив не более 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
Пример 1 вывода:
4
Пример 2 ввода:
6
5
2
2
3
5
7
8
Пример 2 вывода:
6
5. Особенная бусина
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
У Алисы есть нитка бус, состоящая из N бусин. Каждая бусина имеет свой цвет, который задаётся целым числом от 1 до M.
Алисе очень нравится цвет X. Она хочет вырезать из нитки непрерывный фрагмент (подотрезок) так, чтобы в нём бусина её любимого цвета X встречалась ровно один раз. Это позволит ей сделать красивый браслет с единственным ярким акцентом.
Помогите Алисе посчитать, сколько существует различных способов выбрать такой непрерывный фрагмент. Два фрагмента считаются различными, если они отличаются начальной или конечной позицией в исходной нитке бус.
Формат входных данных
В первой строке задано целое число N (1 ⩽ N ⩽ 2 · 105) — количество бусин на нитке.
Во второй строке задано целое число M (1 ⩽ M ⩽ 2 · 105) — количество возможных цветов.
В третьей строке задано целое число X (1 ⩽ X ⩽ M) — любимый цвет Алисы.
В каждой из следующих N строк задано по одному целому числу Ai (1 ⩽ Ai ⩽ 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
Пример 1 вывода:
8
Пример 2 ввода:
4
5
1
2
3
4
5
Пример 2 вывода:
0