Олимпиада по информатике 8–10 классы — пригласительный этап ВсОШ 2026/2027: задания и ответы
Официальный комплект пригласительного этапа Всероссийской олимпиады школьников по информатике для 8–10 классов (2026/2027 учебный год). Задания и решения с критериями оценивания — скачайте PDF или прорешайте онлайн по тексту ниже.
Задания — текст для прорешивания
Текст извлечён из официального PDF автоматически: формулы, таблицы и рисунки могут отображаться неточно — сверяйтесь с документом выше.
Пригласительный этап ВсОШ 2026, информатика (программирование), 8-10 классы
Задания по программированию
. Вам будет предложено пять задач по программированию (можно использовать следующие языки
программирования: Python 3 , C++, Kotlin, PascalABC.NET, C#, Java, Go, PHP, Кумир, Rust). Подробнее о требованиях к программам можно прочитать в инструкции на сайте олимпиады. 2
. Напоминаем, что решения можно сохранять несколько раз. Засчитывается попытка, набравшая
наибольшее количество баллов. Отправить новое решение задачи можно через 30 секунд после предыдущей попытки. 3
. Убедитесь, что ваше решение не выводит никаких иных сообщений, кроме тех, которые описаны
в условии задачи. 4
. Если задача предполагает вывод целого числа, то его следует представить, используя только цифры.
Например, недопустимо использование записи 1000000.0 или 1e6 вместо 1000000.
1/7
№1
100 баллов
Аргайл Ограничение по времени: 1 секунда Аргайл — узор из ромбов или квадратов, расположенных в шахматном порядке и образующих параллельные и поперечные полосы разных цветов. Название происходит от имени шотландского клана Кампбелл в графстве Аргайл. Особенную популярность этот орнамент получил в XX веке. Это случилось благодаря компании «Pringle of Scotland», которая стала выпускать элитный трикотаж с орнаментом «Аргайл», после чего он стал визитной карточкой аристократии. С тех пор узор не выходит из моды. Существует огромное количество цветовых решений этого орнамента. Особенно популярен этот узор на свитерах, жилетах, кардиганах, платьях, шарфах, носках и гетрах.
Сколько квадратов красного и зелёного цветов целиком помещаются на ткани размером n × n?
Формат входных данных Единственная строка входных данных содержит натуральное число n (1 ⩽ n ⩽ 109 ). Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64
-битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.
Формат выходных данных Выведите в двух строках два неотрицательных целых числа — ответ на вопрос задачи. В первой строке выведите количество квадратов красного цвета, во второй — зелёного.
Система оценки Решения, правильно работающие при n ⩽ 105 , будут оцениваться в 50 баллов.
Примеры
3 1 1 4 1 4
Код
Python 3
2/7
№2
100 баллов
Оптом — дешевле? Ограничение по времени: 1 секунда Петя и его друзья собираются отпраздновать успешное окончание учебного года. Для этого они решили приобрести n упаковок апельсинового сока и m упаковок яблочного сока и выделили на эти цели s рублей. Одна упаковка любого сока стоит r рублей. Однако можно приобретать сок коробками. Одна коробка содержит k упаковок сока одного вида и стоит p рублей (известно, что k ⋅ r > p). Друзья хотят приобрести как можно больше упаковок сока на имеющиеся деньги, но так, чтобы при этом было не менее n упаковок апельсинового сока и не менее m упаковок яблочного. Сколько упаковок сока смогут приобрести друзья при таком условии?
Формат входных данных В первой строке содержится целое число n (1 ⩽ n ⩽ 5 ⋅ 105 ) — необходимое количество упаковок апельсинового сока. Во второй строке содержится целое число m (1 ⩽ m ⩽ 5 ⋅ 105 ) — необходимое количество упаковок яблочного сока. В третьей строке содержится целое число r (1 ⩽ r ⩽ 1000) — цена одной упаковки сока (любого вида). В четвёртой строке содержится целое число k (2 ⩽ k ⩽ 106 ) — количество упаковок сока в коробке. В пятой строке содержится целое число p (1 ⩽ p < k ⋅ r ) — цена коробки, содержащей k упаковок сока. В шестой строке содержится целое число s (1 ⩽ s ⩽ 109 ) — количество денег, выделенных на покупку сока.
Формат выходных данных Выведите целое число — максимально возможное суммарное количество упаковок сока, которые получится приобрести. Если невозможно приобрести сок, соблюдая описанные условия, выведите −1 .
Система оценки Решения, правильно работающие, когда хотя бы одна из величин n или m делится на k нацело, будут оцениваться в 25 баллов.
Замечание В первом примере из условия нужно купить 8 упаковок апельсинового сока и 7 упаковок яблочного сока. Одна упаковка стоит 80 рублей, а коробка из 5 упаковок — 370 рублей. На 1110 рублей можно купить 3
коробки сока, например, две коробки апельсинового и одну коробку яблочного. Останется
1400 − 3 ⋅ 370 = 290
рублей: 240 рублей хватит на 3 упаковки яблочного сока (или 2 упаковки яблочного
и 1 — апельсинового), 50 рублей останется. Условия будут выполнены, всего приобретено 3 ⋅ 5 + 3 = 18
упаковок сока.
Во втором примере на 1200 рублей можно приобрести 5 коробок сока по 225 рублей. Если взять три коробки апельсинового сока и две коробки яблочного, то условия будут выполнены. Останется 1200 − 5 ⋅ 225 = 75
рублей, на которые ничего нельзя купить.
В третьем примере на 1100 рублей можно купить 2 коробки сока по 375 рублей: коробку апельсинового и коробку яблочного. Останется 1100 − 2 ⋅ 375 = 350 рублей, на которые нужно купить ещё три упаковки апельсинового и две упаковки яблочного сока. При стоимости упаковки в 80 рублей это сделать нельзя.
Примеры
8 7 80 5 370 1400 18
3/7
8 7 80 5 225 1200 25 8 7 80 5 375 1100 -1
4/7
№3
100 баллов
Арт-объект Ограничение по времени: 1 секунда Арт-объект представляет собой n колонн высотой a 1 , a 2 , …, a n сантиметров. Критики считают, что арт-объект станет выглядеть лучше, если высоты колонн будут идти по неубыванию, то есть высота каждой колонны должна быть не меньше высоты предыдущей колонны (a i ⩾ a i−1 для всех ).
i ⩾ 2
Поскольку порядок колонн нельзя менять (это разрушит замысел автора), колонны можно расположить на лестнице, высота ступеньки которой равна d . При этом на каждой ступеньке будет стоять одна колонна, а первая колонна должна стоять на первой ступеньке. Тогда высота первой колонны a 1 увеличится на d , высота второй колонны a 2 увеличится на 2d , значение a 3 увеличится на 3d и так далее. Чтобы арт-объект не стал слишком громоздким, нужно найти минимальную подходящую высоту ступеньки d , при которой высоты колонн станут неубывающими.
Формат входных данных Первая строка входных данных содержит целое число n (1 ⩽ n ⩽ 2 ⋅ 105 ) — количество колонн. В следующих n строках записаны высоты колонн a i , 1 ⩽ a i ⩽ 109 .
Формат выходных данных Программа должна вывести минимальную подходящую высоту ступеньки d . Если высоты колонн уже неубывают, необходимо вывести число 0 .
Система оценки Решения, правильно работающие при n ⩽ 2 , будут оцениваться в 20 баллов. Решения, правильно работающие при a i ⩽ 10 , будут оцениваться в 30 баллов.
Замечание В первом примере высоты колонн равны 1 , 5 , 2 , 7 , 5 . Если использовать лестницу со ступенькой d = 3, то высоты колонн станут 4 , 11, 11, 19, 20. Если взять ступеньку d = 2, то получатся высоты 3 , 9 , 8 , 15, 15, и тогда колонна номер 2 будет выше колонны номер 3 .
Примеры
5 1 5 2 7 5 3
Код
Python 3
5/7
№4
100 баллов
Длина риса Ограничение по времени: 1 секунда В одном из ресторанов между n поварами возник спор — какой длины должен быть рис? Каждый повар считает по-своему: i -й повар считает, что длина должна быть равна hi миллиметрам. Повар может переубедить другого повара, если представления поваров о длине риса отличаются на единицу (то есть i -й повар может переубедить j-го, если |hi − hj | = 1 ). Если i -й повар переубедит j-го, то значение hj станет равно значению hi . Переубеждённый повар может затем снова изменить своё мнение. Менеджеру по закупкам ресторана нужно закупить рис одной длины. Какому максимальному количеству поваров можно угодить после того, как какие‑то повара смогут переубедить друг друга?
Формат входных данных Первая строка входных данных содержит одно натуральное число n (1 ⩽ n ⩽ 105 ) — количество поваров. Каждая из следующих n строк содержит одно натуральное число hi (1 ⩽ hi ⩽ 109 ) — идеальную длину риса по мнению i -го повара.
Формат выходных данных Программа должна вывести одно число — максимальное количество поваров, которые могут прийти к единому мнению о длине риса.
Система оценки Решения, правильно работающие, когда n ⩽ 103 и все hi различны, будут оцениваться в 20 баллов. Решения, правильно работающие, когда n ⩽ 103 , будут оцениваться в 60 баллов.
Замечание В примере из условия повара имеют следующие предпочтения о длине риса: 2 , 3 , 4 , 2 , 6 , 8 , 7 . Сначала второй повар переубедит третьего в том, что длина риса должна быть равна 3 . Затем первый повар переубедит второго и третьего в том, что длина риса 2 подходящая. Также четвёртый повар считает, что 2 — подходящая длина, поэтому 4 повара сошлись в мнении о том, что длина 2 будет подходящей.
Примеры
7 2 3 4 2 6 8 7 4
Код
Python 3
6/7
№5
100 баллов
Чувство прекрасного Ограничение по времени: 1 секунда Вася — начинающий художник. Поскольку опыта у него немного, сейчас он практикуется в рисовании гармоничных полосок. Каждая полоска, рисуемая Васей, состоит из n последовательных ячеек, каждая из которых может быть покрашена в один из m цветов. Яркостью полоски в таком случае называется сумма модулей разностей цветов соседних ячеек. Например, яркость полоски {3, 1 , 5 , 2} равна |3 − 1| + |1 − 5| + |5 − 2| = 9, а яркость полоски {1, 1 , 2} равна |1 − 1| + |1 − 2| = 1 . Как у любого художника, у Васи очень сильно развито чувство прекрасного, и оно подсказывает ему, что полоска будет тем красивее, чем меньше будет её значение яркости. На текущий момент краски цвета i , имеющейся у Васи, хватит для того, чтобы покрасить не более a i ячеек. Помогите художнику — определите, какую минимальную яркость может иметь полоска, нарисованная Васей.
Формат входных данных В первой строке содержится число n (1 ⩽ n ⩽ 109 ) —размер полоски. Во второй строке содержится число m (1 ⩽ m ⩽ 3 ⋅ 105 ) — количество доступных Васе цветов. В i -й из следующих m строк содержится число a i (0 ⩽ a i ⩽ 109 ) — количество ячеек, на покраску которых хватит краски цвета i , имеющейся у Васи. Гарантируется, что n ⩽ a 1 + ⋯ + a m (т. е. Васе хватит краски, чтобы раскрасить все ячейки).
Формат выходных данных В единственной строке выведите одно число — минимальную яркость, которую может иметь полоска, нарисованная Васей.
Система оценки Решения, правильно работающие при m ⩽ 3, будут оцениваться в 20 баллов. Решения, правильно работающие при n , m ⩽ 6, будут оцениваться в 25 баллов. Решения, правильно работающие при m ⩽ 100, будут оцениваться в 60 баллов. Решения, правильно работающие при m ⩽ 1500, будут оцениваться в 70 баллов.
Примеры
7 5 0 2 3 1 1 3 6 3 1 4 3 1
Код
Python 3
7/7
Ответы и решения — показать
Официальные ответы и критерии оценивания жюри. Сначала решите задания самостоятельно.
Пригласительный этап всероcсийской олимпиады по программированию для 8–10 классов Образовательный центр «Сириус», 18-19 мая 2026
Разбор задач
Задача 1. Аргайл
Первая подзадача: Если посмотреть на получившийся узор, то можно заметить, что новый ряд зелёных квадратов появляется при каждом чётном n, а новый ряд красных — на каждом нечётном, начиная с 3. Таким образом, можно перебрать все промежуточные значения, увеличивая счётчик рядов на 1 при каждом выполнении условия чётности или нечётности для определённого цвета. Такое решение наберёт 50 баллов. n = int ( input ( ) ) red = 0 f o r i in range ( 2 , n + 1 ) : i f i % 2 == 1 : r e d += 1 green = 0 f o r i in range ( 1 , n + 1 ) : i f i % 2 == 0 : g r e e n += 1 print ( r e d ∗∗ 2 ) print ( g r e e n ∗∗ 2 ) Полное решение. Воспользуемся операциями целочисленного деления. Один зелёный квадрат располагается на квадрате 2 × 2, поэтому ответ для этого цвета будет равен (n // 2) ** 2. Если убрать полосы шириной 1 слева и снизу ткани, то ответ для красного цвета сведётся к предыдущему: теперь один красный квадрат располагается на квадрате 2 на 2, поэтому ответ для этого цвета будет равен ((n - 1) // 2) ** 2. n = int ( input ( ) ) r e d = ( ( n − 1 ) // 2 ) ∗∗ 2 g r e e n = ( n // 2 ) ∗∗ 2 print ( r e d ) print ( g r e e n )
Страница 1 из 7
Пригласительный этап всероcсийской олимпиады по программированию для 8–10 классов Образовательный центр «Сириус», 18-19 мая 2026
Задача 2. Оптом — дешевле?
Прежде всего отметим, что всегда выгодно купить коробку вместо k отдельных упаковок сока. Поэтому при необходимости приобрести определённое количество упаковок сока, нужно посчитать количество полных упаковок, взяв частное от деления на k, и остаток от деления на k будет равен количеству отдельных упаковок, которое необходимо приобрести. Рассмотрим сначала случай, когда хотя бы одна из величин n или m делится нацело на k. Для определённости будем считать, что n = boxesN · k, а m = boxesM · k + packsM (при необходимости следует поменять местами n и m в рассуждениях). Это значит, что на апельсиновый сок друзья должны потратить boxesN · p рублей, а на оставшиеся деньги они приобретут максимально возможное количество упаковок яблочного сока. Если это количество окажется не меньше m, то условия задачи будут выполнены. Пример решения. n = int ( input ( ) ) m = int ( input ( ) ) r = int ( input ( ) ) k = int ( input ( ) ) p = int ( input ( ) ) s = int ( input ( ) )
# Тр е б у етс я пе р в о г о с о ка # Тр е б у етс я вто р о г о с о ка # Цена упак о вки с о ка # Колич е ств о упак о в о к с о ка в к о р о б к е # Цена к о р о б ки с о ка # Сумма д ене г
i f n % k != 0 : n , m = m, n boxesN = n // k
# к о р о б о к пе р в о г о с о ка
rem = s − boxesN ∗ p # о станетс я д ене г по с л е прио б р етения пе р в о г о с о ка boxes = rem // p # к олич е ств о к о р о б о к , купл енно е на о ста вшие с я д ень г и packs = ( rem % p ) // r # к олич е ств о упак о в о к , купл енно е на о ста вшие с я д ень г и packsRem = boxes ∗ k + packs о ста вшие с я д ень г и
# с умма рно е к олич е ств о упак о в о к , купл енно е на
i f packsRem >= m: ans = n + packsRem else : ans = −1 print ( ans ) Для полного решения заметим, что нет разницы, на какой вид сока потратить излишек денег. Давайте считать, что первого сока мы купим столько, сколько необходимо, а излишки потратим на покупку максимального количества второго сока. Но возможны два способа приобрести первый сок: приобрести ровно n упаковок целыми коробками и отдельными упаковками или вместо отдельных упаковок приобрести одну дополнительную коробку сока. На оставшиеся деньги приобретается максимальное количество второго сока, как в предыдущем решении. Пример решения на языке Python. n = int ( input ( ) ) m = int ( input ( ) ) r = int ( input ( ) ) k = int ( input ( ) ) p = int ( input ( ) ) s = int ( input ( ) ) ans = −1
# Тр е б у етс я пе р в о г о с о ка # Тр е б у етс я вто р о г о с о ка # Цена с о ка # Кол−в о с о ка в к о р о б к е # Цена упак о вки # Сумма д ене г
boxesN = n // k
# к о р о б о к пе р в о г о с о ка Страница 2 из 7
Пригласительный этап всероcсийской олимпиады по программированию для 8–10 классов Образовательный центр «Сириус», 18-19 мая 2026 packsN = n % k
# упак о в о к пе р в о г о с о ка
rem = s − boxesN ∗ p − packsN ∗ r # о станетс я д ене г по с л е прио б р етения n упак о в о к пе р в о г о с о ка i f rem >=0: boxes = rem // p packs = ( rem % p ) // r i f packs + boxes ∗ k >= m: ans = max( ans , packsN + boxesN ∗ k + packs + boxes ∗ k ) boxesN += 1 # д о б а вим о дну к о р о б ку пе р в о г о с о ка packsN = 0 # а упак о вки прио б р етать не б у д ем rem = s − boxesN ∗ p − packsN ∗ r i f rem >= 0 : boxes = rem // p packs = ( rem % p ) // r i f packs + boxes ∗ k >= m: ans = max( ans , packsN + boxesN ∗ k + packs + boxes ∗ k ) print ( ans )
Задача 3. Арт-объект
При n = 1 последовательность из одной колонны уже неубывающая, поэтому нужно вывести 0. При n = 2, если a0 > a1 , то ответ будет равен a0 − a1 , иначе ответ 0. Разобрав эти два случая, можно набрать 30 баллов. Если высоты колонн небольшие, то можно перебрать значения d. Прибавив к значениям ai нужные значения, проверим, что мы получили неубывающую последовательность. Такие решения будут набирать не менее 30 баллов. Пример такого решения. n = int ( input ( ) ) a = [ int ( input ( ) ) f o r i in range ( n ) ] d = 0 while True : i = 1 while i < n and a [ i − 1 ] <= a [ i ] : i += 1 i f i == n : print ( d ) break fo r i in range ( n ) : a [ i ] += i + 1 d += 1 Для того чтобы набрать полный балл, можно заметить, что если разница между двумя соседними значениями ai − ai+1 положительна, то ответ должен быть не меньше этой разницы. Поэтому минимальное значение ответа будет равно наибольшему из значений ai − ai+1 . Этот максимум можно вычислить сразу при считывании данных, необязательно сохранять все значения ai в массиве, достаточно запоминать только значение высоты предыдущей колонны. Пример такого решения. n = int ( input ( ) ) ans = 0 prev = 0 f o r i in range ( n ) : Страница 3 из 7
Пригласительный этап всероcсийской олимпиады по программированию для 8–10 классов Образовательный центр «Сириус», 18-19 мая 2026 c u r r = int ( input ( ) ) ans = max( ans , prev − c u r r ) prev = c u r r print ( ans )
Задача 4. Длина риса
Отсортируем значения hi по возрастанию, то есть дальше будем считать, что h1 ⩽ h2 ⩽ · · · ⩽ hn . Определим, когда мы можем угодить группе поваров. Пусть есть группа поваров с номерами i1 < i2 < · · · < ik , причём hi1 ⩽ hi2 ⩽ · · · ⩽ hik . Тогда этой группе мы можем угодить тогда и только тогда, когда hij − hi+j−1 ⩽ 1. Сначала i2 -й повар переубедит i1 -го повара, затем i3 -й повар переубедит i1 -го и i2 -го поваров, ..., в конце ik -й повар переубедит i1 -го, i2 -го, ..., ik−1 -го поваров. В этом случае все повара сойдутся во мнении, что рис, по мнению ik -го повара, самый оптимальный. Заметим, что если ij = ij−1 + k и при этом hij − hij−1 ⩽ 1, то hij−1 ⩽ hij−1 +1 ⩽ hij−1 +2 ⩽ ⩽ · · · ⩽ hij−1 +2 = ij , а также модуль разности двух соседних элементов не превосходит 1. Значит, будем искать группу поваров i1 < i2 < · · · < ik , где i2 = i1 + 1, i3 = i1 + 2, · · · , ik = i1 + k − 1, то есть будем рассматривать группу поваров с подряд идущими номерами. Для решения первой подгруппы можно перебрать все группы поваров с индексами i, i + 1, i + 2, · · · , j и проверить, что hj − hi = j − i, и для всех индексов, для которых выполняется это условие, выбрать максимальное значение j − i + 1. Действительно, так как все hi различны, для подходящей группы выполняется hi < hi+1 < · · · hj , причём модуль разности между соседними элементами равен 1. Значит, hi+1 = hi + 1, hi+2 = hi+1 + 1 = hi + 2, · · · , hj = hi + j − i. Найдём разность между первым и последним элементами hj − hi = hi + j − i − hi = j − i. Значит, если выполняется равенство hj − hi = j − i, то группа поваров сможет между собой договориться. Данное решение работает за O(n2 ), так как мы перебираем левую и правую границы группы независимо друг от друга. n = int ( input ( ) ) h = [ int ( input ( ) ) f o r i in range ( n ) ] h . sort () ans = 0 f o r i in range ( n ) : fo r j in range ( i , n ) : i f h [ j ] − h [ i ] == j − i : ans = max( ans , j − i + 1 ) print ( ans ) Во второй подгруппе так же проверять не получится. Может быть, к примеру, ситуация hi = hi+1 = hi+2 , hi+3 = hi + 3, и вроде бы hj − hi = hi + 3 − hi = 3, j − i = 3, но группа подходящей не является. Давайте перебирать левую границу i, а затем перебирать максимально большую правую границу j. Изначально i = j. Если hj+1 − hj ⩽ 1, то увеличим j на единицу. Если в какой-то момент мы дошли до последнего элемента массива или неравенство не выполняется, это значит, что мы нашли максимально большую правую границу. Данное решение работает за O(n · k), где k — ответ на задачу. В худшем случае асимптотика будет равна O(n2 ), если k = n. n = int ( input ( ) ) h = [ int ( input ( ) ) f o r i in range ( n ) ] h . sort () ans = 0 f o r i in range ( n ) : j = i while j < n − 1 and h [ j +1] − h [ j ] <= 1 : j += 1 ans = max( ans , j − i + 1 ) Страница 4 из 7
Пригласительный этап всероcсийской олимпиады по программированию для 8–10 классов Образовательный центр «Сириус», 18-19 мая 2026 print ( ans ) Для решения третьей подгруппы нужно немного оптимизировать идею второй подгруппы. Давайте зафиксируем счётчик count, который показывает количество элементов в группе. Первоначально count = 1 (мы рассматриваем первый элемент). Переберём элементы от первого до последнего. Если разница между очередной длиной и прошлой длиной меньше либо равна 1, увеличим count на единицу. Если же разница больше 1, то это значит, что мы перешли к новой группе, поэтому сбросим значение count = 1. Одновременно с этим, нужно искать максимум из всех значений count. Данное решение работает за O(n log n), так как необходимо отсортировать массив и пройти циклом по его элементам. n = int ( input ( ) ) h = [ int ( input ( ) ) f o r i in range ( n ) ] h . sort () count = 1 ans = 1 f o r i in range ( 1 , n ) : i f h [ i ] − h [ i −1] <= 1 : count += 1 else : count = 1 ans = max( ans , count ) print ( ans )
Задача 5. Чувство прекрасного
Пусть мы выбрали набор цветов (чисел) для полоски. Тогда яркость будет минимальной, если цвета в полоске упорядочить по неубыванию. Пусть полоска состоит из ячеек с цветами c1 ⩽ c2 ⩽ ... ⩽ cn , тогда яркость такой полоски равна cn − c1 . Также заметим, что невыгодно «пропускать» цвета. То есть, если для выбранной полоски есть какой-то цвет c, причём c1 < c < cn , то в наилучшем ответе все ячейки цвета c должны присутствовать (цвет c должен быть использован ровно ac раз). Иначе можно выкинуть из полоски последнюю ячейку цвета cn и добавить ячейку цвета c; для такой полоски ответ не будет хуже. Рассмотрим большую полоску, состоящую из цвета 1, повторённого a1 раз, затем из цвета 2, повторённого a2 раз и т.д. В этой полоске нужно выбрать n подряд идущих клеток с минимальной разницей значений в правой и левой клетках. Решение, реализующее этот процесс, имеет сложность O(a1 + a2 + ... + am ) и набирает 25 баллов. Пример такого решения. n = int ( input ( ) ) m = int ( input ( ) ) c = [] f o r i in range ( 1 , m + 1 ) : c += [ i ] ∗ int ( input ( ) ) ans = m + 1 f o r i in range ( len ( c ) − n + 1 ) : ans = min( ans , c [ i + n − 1 ] − c [ i ] ) print ( ans ) Но сумма a1 + a2 + ... + am может достигать 1014 , что очень много. Для того чтобы получить больше баллов, нужно избавиться от любых значений ai в оценке сложности. В предложенном решении в оптимальной полоске мы использовали все цвета полностью, кроме, быть может, цвета, в который покрашены первая и последняя клетки полоски. Но здесь тоже можно применить уже использованную идею: если цвет c1 использован не полностью, то уберём последнюю Страница 5 из 7
Пригласительный этап всероcсийской олимпиады по программированию для 8–10 классов Образовательный центр «Сириус», 18-19 мая 2026 клетку цвета cn и добавим клетку цвета c1 . То есть оптимальный ответ можно искать только среди полосок следующего вида. Выберем какой-то начальный цвет полоски c. Добавим в полоску все клетки цвета c. Если размер полоски меньше n, добавим клетки цвета c + 1. Если по-прежнему не набралось n клеток, добавим все клетки цвета c + 2, и т.д. То есть мы будем использовать все цвета полностью, пока не наберётся n клеток. Поэтому решение задачи сводится к тому, что в массиве a нужно выбрать два индекса i ⩽ j — цвет первой и последней клеток полоски, при этом краски цветов от i до j должно быть достаточно для покраски n клеток, то есть ai + ... + aj ⩾ n. Тогда яркость такой полоски равна j − i, и необходимо найти минимальное значение j − i для всех подходящих пар (i, j). Если перебирать пары индексов (i, j) и сумму чисел ai + ... + aj считать циклом (или, например, функцией sum в Python), то сложность решения получится O(m3 ). Пример такого решения. n = int ( input ( ) ) m = int ( input ( ) ) a = [ int ( input ( ) ) f o r i in range (m) ] ans = m f o r i in range (m) : fo r j in range ( i , m) : sm = sum( a [ i : j +1]) i f sm >= n : ans = min( ans , j − i ) print ( ans ) Это решение можно улучшить, если сумму внутри цикла не пересчитывать заново, а при увеличении j на 1 добавлять к сумме sm значение одного элемента aj . Сложность такого решения O(m2 ). Также цикл по j можно заканчивать, когда сумма sm превысила n, поскольку добавлять новые цвета к такой полоске бессмысленно. Такое решение набирает 70 баллов. n = int ( input ( ) ) m = int ( input ( ) ) a = [ int ( input ( ) ) f o r i in range (m) ] ans = m f o r i in range (m) : sm = 0 fo r j in range ( i , m) : sm += a [ j ] i f sm >= n : ans = min( ans , j − i ) break print ( ans ) Чтобы набрать 100 баллов, нужно использовать метод двух указателей. Для этого заметим, что если для какого-то значения i нашли подходящее наименьшее значение j, то при увеличении i значение j не изменится или увеличится. Поэтому после увеличения i запустим цикл, увеличивающий значение j, пока новая сумма не станет больше или равна n. При каждом увеличении j к сумме добавляется aj , а при увеличении i сумма уменьшается на ai . Такое решение имеет сложность O(m). Пример такого решения. n = int ( input ( ) ) m = int ( input ( ) ) a = [ int ( input ( ) ) f o r i in range (m) ] j = 0 sm = 0 ans = m f o r i in range (m) : while j < m and sm < n : Страница 6 из 7
Пригласительный этап всероcсийской олимпиады по программированию для 8–10 классов Образовательный центр «Сириус», 18-19 мая 2026 sm += a [ j ] j += 1 i f sm >= n : ans = min( ans , j − i − 1 ) sm −= a [ i ] print ( ans )
Страница 7 из 7