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

Школьный этап всероcсийской олимпиады по информатике для 9-11 классов

22 октября 2024

Задача 3. Красная Шапочка на болоте

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

1 секунда

Красная Шапочка отправилась на болото для сбора клюквы, чтобы испечь пирожки для ба-

бушки. Клюквенное болото представляет собой координатную прямую. Берег, на котором стоит

девочка, имеет координату 0, а клюквенная поляна - координату N + 1. В точках с координата-

ми 1, 2, . . . , N расположены кочки. Первоначально у девочки E единиц энергии. Красная Шапочка

может прыгнуть из точки x в точку y (x < y), потратив на это (y - x) единиц энергии, то есть

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

кочке с координатой i, она получает a_iединиц энергии (при этом значение a_iможет оказаться отри-

цательным, тогда энергия Красной Шапочки уменьшится при приземлении). Нельзя, чтобы энергия

Красной Шапочки в какой-либо момент оказалась меньше нуля. Например, Красная Шапочка не

может прыгнуть с кочки 1 на кочку 3, имея одну единицу энергии, вне зависимости от того, сколь-

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

единицы энергии.

Так как Красной Шапочке ещё надо вернуться обратно, девочке интересно, какое максимальное

количество энергии у неё может оказаться, когда она достигнет поляны (точки с координатой N+1).

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

Первая строка входных данных содержит целое число E - первоначальный запас энергии Крас-

ной Шапочки, 1 E

10⁹.

Вторая строка входных данных содержит целое число N - количество кочек на болоте,

1 N

10⁵.

Следующие N строк содержат по одному целому числу a_i- энергия, которую получает Красная

Шапочка на i-й кочке, -2000 a_i

2000.

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

Программа должна вывести одно число - максимальное количество единиц энергии, которое

останется у Красной Шапочки после достижения клюквенной поляны. Если девочка не сможет

достигнуть цели, выведите одно число «-1» (без кавычек).

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

Решения, правильно работающие при N

15, будут оцениваться в 20 баллов.

Решения, правильно работающие при N

900, будут оцениваться в 70 баллов.

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

Примеры

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

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

-1

100

-1

Замечание

В первом примере три кочки и первоначально 2 единицы энергии у Красной Шапочки. Она

прыгает на кочку 1, что требует 1 единицу энергии, и у неё остаётся 1 единица энергии. На кочке

1 девочка получает 1 единицу энергии, и у неё становится 2 единицы энергии. Затем она прыгает

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

Школьный этап всероcсийской олимпиады по информатике для 9-11 классов

22 октября 2024

Задача 4. Деление шоколадки

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

1 секунда

У Маши есть прямоугольная шоколадка, состоящая из m × n квадратных долек. Маша хочет

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

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

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

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

этом куске.

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

Программа получает на вход три натуральных числа, каждое в отдельной строке: m, n и k. Все

числа - целые положительные, при этом m и n не превосходят 10⁶, а k mn.

Обратите внимание на то, что значение mn, а, значит, и значение k в этой задаче

может превышать возможное значение 32-битной целочисленной переменной, поэтому

необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке

Pascal, тип long long в C++, тип long в Java и C#).

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

Программа должна вывести одно целое число - максимально возможное количество долек в

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

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

Решения, правильно работающие при m

1000 и n

1000, будут оцениваться в 60 баллов.

Пример

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

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

Замечание

В примере из условия нужно разделить шоколадку 4 × 5 на 4 кусочка. Самый большой кусочек

будет состоять из 16 долек, как показано на картинке.

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

Школьный этап всероcсийской олимпиады по информатике для 9-11 классов

22 октября 2024

Задача 5. Кодовый замок

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

1 секунда

В разведывательное управление доставили сейф с секретной информацией, кодовый замок на

котором открывается комбинацией из n цифр, каждая цифра может принимать b различных зна-

чений от 0 до b - 1. Код неизвестен, однако разведчики передали несколько донесений о том, что

сумма цифр кода в некоторых заданных позициях равна какому-то известному числу. Используя

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

удовлетворяющих этим условиям.

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

Первая строка входныхданных содержит число b - количество различных значений однойциф-

ры кода, 2 b

10. Вторая строка содержит число n - количество цифр в коде, n ) 1, bn

60 000.

Третья строка содержит число t - количество имеющихся донесений о сумме каких-то цифр кода,

t )

Следующие 2t строк содержат информацию об имеющихся донесениях. Каждое донесение состо-

ит из двух строк. Первая из этих строк («маска цифр») содержит n символов, записанных слитно

и равных «0» или «1», где цифра «1» обозначает, что в донесении говорится об этой цифре кода.

Например, маска цифр «01011» означает сумму цифр, стоящих в коде на 2-й, 4-й и 5-й позициях. Во

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

Гарантируется, что каждая маска цифр содержит хотя бы одну единицу и что все маски цифр

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

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

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

творяют всем донесениям.

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

Решения, правильно работающие, когда n

4 и каждая маска цифр содержит ровно один символ

«1», будут оцениваться в 28 баллов.

Решения, правильно работающие, когда n

4, будут оцениваться в 64 балла.

Пример

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

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

110

011

Замечание

В примере из условия каждая цифра кода может принимать 8 различных значений от 0 до 7,

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

и второй цифры кода равна 7, из второго донесения известно, что сумма второй и третьей цифры

кода равна 12. Существуют 3 кода, удовлетворяющие этим условиям: «075», «166», «257».

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

Школьный этап всероcсийской олимпиады по информатике для 9-11 классов

22 октября 2024

Разбор задач

Задача 1. Качели

Первую группу тестов можно пройти при помощи переборного решения. Будем перебирать зна-

чение ответа (массу камня) в переменной ans. Для каждого значения ans проверим, смогут ли дети

качаться с камнем данной массы. Переберём все возможные варианты размещения детей и камня,

всего таких способов 6 (тремя способами можно выбрать одного ребёнка, который сидит на одном

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

посчитаем модуль разности весов на концах качелей, если он не превосходит d, то ответ найден.

Пример такого решения.

a = int ( input ( ) )

b = int ( input ( ) )

c = int ( input ( ) )

d = int ( input ( ) )

ans = 0

while True :

i f ( abs ( a+b-c-ans ) <= d

abs ( a+b-c+ans ) <= d

or abs ( b+c-a-ans ) <= d

abs ( b+c-a+ans ) <= d

or abs ( a+c-b-ans ) <= d

or abs ( a+c-b+ans ) <= d ) :

print ( ans )

break

ans += 1

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

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

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

сложности O(1).

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

посадить самого тяжёлого ребёнка, а на другую сторону - двух других детей. Посчитаем разницу

масс на концах качелей в этом случае, если она не превосходит d, то камень не нужен, и ответом

будет 0. Иначе вычтем из этой разницы значение d, это и будет ответ.

Пример такого решения.

a = int ( input ( ) )

b = int ( input ( ) )

c = int ( input ( ) )

d = int ( input ( ) )

s i d e 1 = max( a , b , c )

s i d e 2 = a + b + c - s i d e 1

print (max( 0 , abs ( s i d e 1 - s i d e 2 ) - d ) )

Задача 2. Фонари

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

можно. Один фонарь первого типа освещает 2x + 1 домов, второго типа - 2y + 1 домов. Поэтому

сначала проверим, существует ли решение задачи, то есть посчитаем максимальное число домов,

которые могут освещаться a фонарями первого вида и b фонарями второго вида. Если это число

меньше n, то нужно вывести -1. Иначе получим ответ при помощи «жадного» алгоритма: для

минимизации числа фонарей выберем фонарь, который освещает больше домов, и разместим его

так, чтобы множество домов, которое он освещает, непосредственно примыкало к уже освещённым

домам. Повторим этот процесс, пока все дома не станут освещены.

В приведённом ниже решении мы предполагаем, что фонари первого вида освещают большее

число домов, то есть x ) y. Если это не так, то поменяем два вида фонарей местами. Поэтому

будем стараться всегда использовать фонарь первого вида. В переменной last_lighted хранится

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

Школьный этап всероcсийской олимпиады по информатике для 9-11 классов

22 октября 2024

номер последнего освещённого дома. Цикл продолжается, пока не все дома освещены, то есть пока

last_lighted < n. Если есть ещё фонари первого вида, то используется фонарь первого вида, и

количество освещённых домов увеличивается на 2x + 1 для фонарей первого типа и на 2y + 1 для

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

дома в выводе не может быть больше n.

Пример решения.

n = int ( input ( ) )

a = int ( input ( ) )

x = int ( input ( ) )

b = int ( input ( ) )

y = int ( input ( ) )

i f a ∗ ( 2 ∗ x + 1) + b ∗ ( 2 ∗ y + 1) < n :

print ( -1)

else :

i f x < y :

x , y = y , x

a , b = b , a

l a s t _ l i g h t e d = 0

while l a s t _ l i g h t e d < n :

i f a > 0 :

print (min( n , l a s t _ l i g h t e d + x + 1 ) , x )

l a s t _ l i g h t e d += 2 ∗ x + 1

a-= 1

else :

print (min( n , l a s t _ l i g h t e d + y + 1 ) , y )

l a s t _ l i g h t e d += 2 ∗ y + 1

b -= 1

Задача 3. Красная Шапочка на болоте

В подгруппе N

15 можно написать переборное решение. Рассмотрим все подмножества кочек,

таких подмножеств будет 2^N. Пусть Красная Шапочка прыгает на выбранные кочки. Проверим,

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

остаточной энергией.

В подгруппе N

900 предполагается решение сложности O(N²) с использованием идеи динами-

ческогопрограммирования. Пустьf (i) - максимальное количество энергии,котороеможетостаться

у Красной Шапочки, когда она окажется в точке с координатой i. Тогда f (0) = E, f (N + 1) - ответ

на задачу. Будем последовательно вычислять f (1), f (2), . . . , f (N +1). Для вычисления f (i) рассмот-

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

равно f(j) - (i - j) + a_i. Переберём все j от 0 до i - 1 и выберем наибольшее возможное значение.

f (i) = max f (j)

j) + a_i

j<i

При этом удобно считать, что an+1 = 0 (поляна обрабатывается как обычная кочка с нулевой

дополнительной энергией), а также необходимо проверить, что значение f (j) - (i - j) ) 0, иначе

Красная Шапочка не сможет прыгнуть из j в i.

Пример такого решения.

import sys

e = int ( input ( ) )

n = int ( input ( ) )

a = [ 0 ] + [ int ( input ( ) ) for i in range ( n ) ] + [ 0 ]

f = [ e ] + [ 0 ]

∗ ( n + 1 )

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

Школьный этап всероcсийской олимпиады по информатике для 9-11 классов

22 октября 2024

for i in range ( 1 , n + 2 ) :

m = -1

for j in range ( 0 , i ) :

m = max(m, f [ j ] - ( i - j ) )

i f m < 0 :

print ( -1)

sys . e x i t ( 0 )

f [ i ] = m + a [ i ]

print ( f [ n + 1 ] )

Для дальнейшего решения задачи заметим, что какие бы кочки Красная Шапочка ни посетила,

у неё всегда уйдёт ровно N + 1 единица энергии на совершение всех прыжков из точки 0 в точку

N + 1. Действительно, пусть она посетила кочки с координатами 0 < x₁< x₂< · · · < x_k< N + 1,

тогда суммарные затраты энергии равны

(x₁- 0) + (x₂- x₁) + · · · + (x_k- xk-1) + (N + 1 - x_k) = N + 1 - 0 = N + 1

Значит, количество энергии, оставшееся у Красной Шапочки после достижения поляны, составит

E+S-(N+1), где S - суммарная энергия, которую КраснаяШапочка получила на всех посещённых

кочках. Следовательно, необходимо максимизировать значение S. Для этого достаточно посетить

все такие кочки i, у которых a_i> 0, проверив, что у Красной Шапочки достаточно энергии, чтобы

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

Ниже приведено решение на языке Python. Значения a_iможно не сохранять в массиве, а обра-

батывать их сразу после считывания. Значение s сразу проинициализируем начальным значением

энергии Красной Шапочки и будем добавлять к нему положительные значения a_i. Тогда для про-

верки того, что Красная Шапочка может попасть в точку i достаточно проверить условие s - i )

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

нуля в i.

import sys

s = int ( input ( ) ) # Сумма э не р гий в начале и на вс е х по ложительных ко чках

n = int ( input ( ) )

for i in range ( 1 , n + 1 ) :

a i = int ( input ( ) )

i f a i > 0 :

# На этой кочке нужно остано витс я

i f s - i < 0 :

# Количество э не ргии , что бы д о стичь кочки i

print ( -1)

# Если s - i отрицательно , то не льзя д о стичь i

sys . e x i t ( 0 )

s += a i

;

i f s - ( n + 1 ) < 0 :

# Эне р гия , не о бхо димая для д о стижения поляны

print ( -1)

# Если она отрицательна , то нельзя д о стичь поляны

else :

print ( s - ( n + 1 ) )

# иначе выводим отв ет

Задача 4. Деление шоколадки

Должен получиться большой кусок и ещё k - 1 маленьких кусочков, поэтому размер большого

куска будет не более, чем mn - k + 1.

Чтобы набрать 60 баллов можно перебирать размеры большого куска a×b, при этом 1 a m,

1 b n. Проверим, что ab mn - k + 1 и запомним наибольшее подходящее значение ab.

Такое решение будет иметь сложность O(mn). Пример такого решения.

m = int ( input ( ) )

n = int ( input ( ) )

k = int ( input ( ) )

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

Школьный этап всероcсийской олимпиады по информатике для 9-11 классов

22 октября 2024

ans = 1

for a in range ( 1 , m + 1 ) :

for b in range ( 1 , n + 1 ) :

i f a ∗ b <= m ∗ n - k + 1 :

ans = max( ans , a ∗ b )

print ( ans )

Чтобы набрать 100 баллов, необходимо избавиться от одного из циклов. Заметим, что при фик-

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

превосходящей mn-k + 1 можно получить, взяв целую часть от деления mn-k + 1 на a. Необходи-

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

подходящего b минимум из значений b и (m ∗ n - k + 1) // a. Такое решение будет иметь сложность

O(m). Также допустимо перебирать значение длины другой стороны за O(n) или взять наименьшую

из двух сторон n или m.

m = int ( input ( ) )

n = int ( input ( ) )

k = int ( input ( ) )

ans = 1

for a in range ( 1 , m + 1 ) :

b = min( n , (m ∗ n - k + 1 )

// a )

ans = max( ans , a ∗ b )

print ( ans )

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

превосходит mn - k + 1, помещающийся внутри прямоугольника m × n. Осталось доказать, что

такой прямоугольник является ответом на задачу, то есть его и ещё k - 1 кусков можно получить

разламыванием прямоугольника m × n.

Рассмотрим разные значения k. При k = 1 кусок всего один, его площадь не превосходит mn,

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

При k ) 3 получить большой прямоугольник можно двумя разломами - вдоль каждой из сторон

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

больше двух дополнительных кусков, то есть при k > 3, то станем разламывать меньшие куски на

части. Один дополнительный разлом увеличивает число кусков на 1. Куски удастся разламывать

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

нужное количество частей.

Наконец, при k = 2 шоколадку нужно разломить на две части, сделав одну из частей как можно

больше. Отломим от целой шоколадки полоску 1 × m или 1 × n, в зависимости от того, какое из

значений m или n меньше. Тогда большой кусок будет иметь размер (m - 1) × n или m × (n - 1). Но

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

прямоугольнике m×n, но имеющий меньшую площадь, то есть и в этом случае приведённое решение

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

Задача 5. Кодовый замок

Общее количество возможных кодов равно bⁿ, так как каждая из n цифр может принимать b

различных значений.

В первой подгруппе все маски цифр имеют специфический вид, они содержат ровно одну еди-

ницу. То есть каждое полученное донесение задаёт фиксированное значение для одной цифры кода.

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

раз, то есть при наличии k ограничений количество подходящих кодов сократится в b^kраз и станет

равно bn-k. И такое простое решение набирает 24 балла.

b = int ( input ( ) )

n = int ( input ( ) )

t = int ( input ( ) )

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

Школьный этап всероcсийской олимпиады по информатике для 9-11 классов

22 октября 2024

print ( b ∗∗ ( n - t ) )

Но это решение проходит не все тесты первой группы, потому что не учитывает тот случай,

когда какое-то ограничение делает все коды невозможными. Учитывая, что каждая маска состоит

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

значение одной цифры, то есть больше или равно b. Достаточно проверить это условие и если оно

выполняется, то ответ будет равен 0. Такое решение проходит все тесты первой группы.

b = int ( input ( ) )

n = int ( input ( ) )

t = int ( input ( ) )

ans = b ∗∗ n

for i in range ( t ) :

mask = input ( )

s = int ( input ( ) )

i f s >= b :

ans = 0

else :

ans //= b

print ( ans )

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

поступивших донесений. Если рассматривать код, как запись числа в системе счисления с осно-

ванием b, то значение такого числа может быть от 0 до bⁿ(не включая верхнюю границу). Будем

хранить коды в виде целых чисел, при этом цифры кода мы можем получить при помощи алгоритма

перевода числа в систему счисления с основанием b, то есть делением на b в цикле n раз. Затем про-

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

представление числа в системе счисления с основанием b, посчитаем сумму цифр кода, стоящих на

указанных в донесении позициях и если эта сумма не соответствует донесению, то пометим код, как

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

Пример такого решения. В списке good_code размера bⁿхранится для каждого кода число 1,

если этот код соответствует всем донесениями, или число 0 в противном случае.

b = int ( input ( ) )

n = int ( input ( ) )

good_code = [ 1 ] ∗ b∗∗n

= int ( input ( ) )

for j in range ( t ) :

mask = input()

sum_ digits

= int ( input ( ) )

for code in range ( b∗∗n ) :

saved_code = code

s = 0

for i in range ( n ) :

i f mask [ i ] ==

’ 1 ’ :

s += code % b

code //= b

i f s

!= sum_ digits :

good_code [ saved_code ] = 0

print (sum( good_code ) )

Но поскольку число донесений может достигать 2ⁿ- 1, сложность такого решения будет bⁿ2ⁿn,

что уже очень много для максимального случая при b = 2, n = 15. Для полного решения необходи-

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

условий. Поэтому сохраним в списке только те коды, которые соответствуют всем рассмотренным

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

Задача 1. Порядок во всём

Вася - очень порядочный мальчик, он любит порядок во всём.

У него в тетради есть столбик натуральных чисел:

701

546

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

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

При этом Вася ничего не хочет зачёркивать, поэтому единственное, что ему остаётся, - это

дописать цифры в конец этих чисел. Например, если в тетради записано число 12, то Вася может

сделать из него числа 120, 121, 1200, 12999 и т.п., то есть любые числа, которые начинаются с 12, а

может и оставить число 12.

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

него получились.

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

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

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

Задача 2. Треугольники

Есть клетчатая полоска шириной в 1 клетку и длиной в n клеток. Внутри каждой клетки провели

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

ми или диагоналями клеток.

Например, для полоски длиной n = 2 получатся 18 треугольников, все они изображены на

рисунке.

Ответом на эту задачу является некоторое выражение, которое может содержать целые чис-

ла, переменную n, операции сложения (обозначаются +), вычитания (обозначаются -), умножения

(обозначаются ∗), деления (обозначаются /) и круглые скобки. Запись вида 2n для обозначения

произведения числа 2 и переменной n некорректна, нужно писать 2 * n.

Ваше выражение должно давать правильный ответ для любого натурального n.

Пример правильной формы записи ответа:

n ∗ (2 ∗ n - 8)

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

Задача 3. Электронное табло

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

жать двузначные числа от 00 до 99 (однозначные числа дополняются слева нулём). Табло можно

управлять при помощи трёх кнопок.

Нажатие на кнопку «+» увеличивает число на табло на 1. Если на табло уже горело число 99,

то оно не меняется.

Нажатие на кнопку «-» уменьшает число на табло на 1. Если на табло уже горело число 00, то

оно не меняется.

Нажатие на кнопку «∗» меняет две цифры на табло местами. Например, если на табло горело

число 53, то после нажатия на «∗» там будет гореть число 35.

Первоначально на табло горит число 00. Найдите самую короткую последовательность нажатий

кнопок, которая получает из числа 00 следующие числа:

23;

38;

65;

84;

99.

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

дого из данных чисел из числа 00. Каждая строка ответа должна состоять только из символов

«+», «-», «∗». Чем короче будет ваша последовательность, тем больше баллов вы получите. Если

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

удовлетворяющую условию, например «+».

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

Задача 4. 90 минут

В московском транспорте можно оплачивать проезд при помощи тарифа «Кошелёк» карты

«Тройка». Есть два вида тарифа:

• «Единый» (57 рублей) - одна поездка на любом виде транспорта;

• «90 минут» (85 рублей) - не более одной поездки на метро и любое количество поездок на

наземном транспорте в течение не более 90 минут с момента начала первой поездки (между

началом поездки и началом первой поездки по тарифу «90 минут» должно пройти не более 90

минут).

Смена тарифа происходит автоматически: при первой поездке списывается 57 рублей, и если

следующая поездка была совершена в течение 90 минут, причём это не повторная поездка на метро,

то с кошелька списывается 28 рублей (в сумме получается 85 рублей) и карта переключается на

тариф «90 минут». Последующие поездки, удовлетворяющие условиям тарифа «90 минут», будут

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

поездки прошло более 90 минут, то с карты будет списано 57 рублей по тарифу «Единый», затем,

возможно, карта опять переключится на тариф «90 минут» и т. д.

Таким образом, каждая поездка может приводить к списанию 57 рублей (тариф «Единый»),

28 рублей (переключение на тариф «90 минут») или 0 рублей (бесплатная поездка по тарифу «90

минут»).

Вам дана информация о 1000 совершённых поездках. Определите сумму списания с карты при

каждой поездке.

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

файл с данными в одном из двух форматов: Microsoft Excel (XLSX) или LibreOffice Calc (ODS).

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

любые другие средства вашего компьютера.

Столбец A электронной таблицы содержит время поездки в формате h:mm, то есть сначала

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

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

Столбец B содержит одну букву - вид поездки. Буква «M» (английская) обозначает поездку на

метро, буква «A» (английская) обозначает поездку на наземном транспорте.

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

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

скопируйте в буфер обмена и вставьте в поле для ввода ответа.

Ваш ответ будет принят на проверку, если он будет содержать 1000 строк и в каждой строке

будет только одно число.

Рассмотрим пример. Пусть дана следующая таблица с информацией о поездках.

0:20

0:40

1:40

2:00

2:20

2:30

2:50

4:20

Тогда ответ будет таким:

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

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

переключится на тариф «90 минут», и с карты спишется 28 рублей, поэтому третья поездка на

наземном транспорте будет бесплатной. Четвёртая поездка на наземном транспорте произойдёт по

тарифу «Единый», потому что разница между временем этой поездки (2:00) и временем первой

поездки по тарифу «90 минут» (0:20) больше 90 минут. При пятой поездке на наземном транспорте

произойдёт переключение на тариф «90 минут», шестая поездка на метро будет бесплатной, седьмая

поездка на метро будет по тарифу «Единый», потому что в тарифе «90 минут» уже была поездка

на метро. Восьмая поездка на наземном транспорте пройдёт по тарифу «90 минут», потому что

разница времён 4:20 и 2:50 составляет ровно 90 минут.

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

Задача 5. Очень большая кольцевая линия

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

0.5 секунд

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

256 мегабайт

В Москве построили новую кольцевую линию метро. Она столь большая, что станции на ней не

имеют названий, а имеют только номера. Всего на линии n станций, они пронумерованы числами

от 1 до n по кругу, и за станцией номер n идёт станция номер 1.

Новая линия проходит мимо дома Тани и её школы. Таня живёт на станции номер a, а школа

находится на станции номер b. Определите, сколько времени понадобится Тане на дорогу на метро,

если между двумя соседними станциями поезд движется 1 минуту (временем стоянки поезда следует

пренебречь). На поезде можно передвигаться в любом из двух направлений кольцевой линии.

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

Первая строка входных данных содержит число n - количество станций на линии (2 n

10⁹).

Вторая строка содержит номер станции a, где живёт Таня (1 a n). Третья строка содержит

номер станции b, где находится школа (1 b n).

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

Программа должна вывести одно целое число.

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

Решения, правильно работающие, когда n

100, будут оцениваться в 60 баллов.

Примеры

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

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

Замечание

В первом примере на дорогу понадобится 2 минуты: 7 - 6 - 5. Во втором примере на дорогу

понадобится 3 минуты: 8 - 9 - 1 - 2.

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

Задача 6. Речные прогулки

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

0.5 секунд

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

256 мегабайт

Вдоль течения реки размещены n пристаней, пронумерованных числами от 1 до n. Пристань

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

реки, расстояние между соседними пристанями равно 1 км.

Для развития туризма решено открыть два прогулочных речных маршрута. Маршруты будут

начинаться на одной из промежуточных пристаней (пристани номер 1 или n не могут быть началь-

ными точками маршрутов), один маршрут будет идти вверх по течению реки к пристани номер 1,

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

маршрутах нет.

Для подъёма вверх по течению реки судно тратит a минут на один километр, а для спуска вниз

по течению реки - b минут на один километр. Определите, на какой пристани должны начинать-

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

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

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

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

2 · 10⁹) - общее количество

пристаней на маршруте. Вторая строка содержит число a - время подъёма судна на один километр

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

течению, 1 b < a

2 · 10⁹.

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

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

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

бой из них.

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

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

в 60 баллов.

Пример

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

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

Замечание

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

по течению судно поднимется за (3 - 1) × 7 = 14 минут, а вниз по течению реки спустится за

(8 - 3) × 3 = 15 минут. Разница в продолжительности маршрутов составит 1, меньшей разности в

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

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

Задача 7. Благоустройство

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

1 секунда

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

256 мегабайт

Рядом с Очень большой кольцевой линией построили новую дорогу, вдоль которой необходи-

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

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

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

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

Введём на улице координатную прямую с единицей, равной 1 метру. Тогда возможная позиция

для i-го дерева имеет координату x_i, а расстояние между двумя деревьями с координатами x_iи x_j

равно |x_i- x_j|.

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

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

деревьями, 1 d

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

n, 1

10⁵. Следующие n строк содержат n различных чисел x_i(1 x_i

10⁹) - возможные

координаты деревьев в порядке возрастания.

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

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

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

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

Решения, правильно работающие, когда n

10, d

10 и все x_i

10, будут оцениваться в 20

баллов.

Решения, правильно работающие, когда n

100, d

100 и все x_i

100, будут оцениваться в 40

баллов.

Решения, правильно работающие, когда n

100 без дополнительных ограничений на d и x_i,

будут оцениваться в 60 баллов.

Пример

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

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

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

Разбор задач

Задача 1. Порядок во всём

Если очередное число уже больше или равно предыдущего числа (после дописывания цифр к

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

(началом) предыдущего числа, то нужно дописать цифры так, чтобы оно стало равно предыдущему

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

или на 1 большей длины. Ответ:

300

820

6300

7010

54600

Задача 2. Треугольники

Внутри каждого единичного квадрата можно выбрать 4 треугольника площади ¹и 4 треуголь-

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

площади 1. Пару соседних квадратов можно выбрать n - 1 способом. Итого 4n + 4n + 2(n - 1).

Ответ (можно записать в виде любого эквивалентного выражения): 8 ∗ n + 2 ∗ (n - 1).

Задача 3. Электронное табло

В первом задании необходимо выполнить две операции «+», чтобы получить цифру 2 на послед-

нем месте, затем поменять их местами, получится 20, затем получить 23. Ответ на первое задание

(получить 23): + + ∗ + ++.

Во втором задании вторая цифра числа большая, поэтому лучше получить число 38 из числа 40

вычитанием числа 2. Ответ на второе задание (получить 38): + + + + ∗ - -.

Используя соображение, что для получения больших цифр лучше использовать операцию вы-

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

например, для получения числа 84, лучше получить число 48 из числа 50, затем переставить цифры

числа в обратном порядке.

Ответ на третье задание (получить 65): + ∗ - - - ∗ - - - - -.

Ответ на четвёртое задание (получить 84): + + + + + ∗ - - ∗.

Ответ на пятое задание (получить 99: + ∗ - ∗ - ∗ +.

Задача 4. 90 минут

Добавив в таблицу первую строку для записи заголовков. Будем использовать несколько вспо-

могательных столбцов.

В столбце C посчитаем время поездки в минутах относительно начала для удобства

вычисления разности времён двух поездок. Это можно сделать при помощи формулы

=LEFT(A2;LEN(A2)-3)

∗

60+RIGHT(A2;2).

Поездки будут разбиваться на группы, соответствующие одному тарифу. Для того чтобы тари-

фицировать одну поездку, нам нужно знать время первой поездки в этой группе (будем записывать

его в столбце D) и количество поездок на метро в этой группе (в столбце E). В следующих двух

столбцах будут записаны логические выражения, определяющее вид поездки. В столбце F будем

записывать TRUE для первой поездки в группе (то есть для поездок по тарифу 57 рублей), в столб-

це G будем записывать TRUE для второй поездки по тарифу «90 минут» (то есть для поездок по

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

тарифу 28 рублей). Строку 2 таблицы можно заполнить явно, записав в F2 значение TRUE, а в

G2 - FALSE.

Поездка будет оплачена по тарифу «единый», то есть будет первой поездкой в группе, при выпол-

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

более 90 минут или количество поездок на метро в предыдущем билете вместе с этой поездкой стало

больше 1. Поэтому в ячейку C3 можно написать формулу =OR(C3-D2>90;E2+(B3="M")>1).

Поездка будет оплачена по тарифу 28 рублей, если предыдущая поездка была оплачена по та-

рифу «единый», а для этой поездки условие оплаты её по тарифу «единый» не было выполнено.

Поэтому в ячейку G3 можно записать формулу =AND(F2;NOT(F3)).

Эти формулы используют данные из столбцов D и E предыдущей строки. Теперь пересчитаем эти

значения в текущей строке. Они зависят от того, была ли эта поездка первой поездкой по тарифу, то

есть от значения в столбце F. В ячейку D3 запишем формулу =IF(F3;C3;D2), в ячейку E3 запишем

формулу =IF(F3;0;E2)+(B3="M").

Наконец, посчитаем стоимость поездки. Она будет равна 57 для поездок, у которых записано

TRUE в столбце F, или 28 рублей для поездок, у которых записано TRUE в столбце G. Для вычис-

ления этого значения можно записать формулу =F3∗57+G3∗28 в ячейку H3.

Наконец, формулы из ячеек C3:H3 можно скопировать в строки 4-1001 таблицы. После этого

числа из столбца H будут ответом на задание.

Задача 5. Очень большая кольцевая линия

Расстояние между станциями с номерами a и b равно |a-b|, если не проезжать участок от станции

n до станции 1. Если же поехать в другом направлении, то расстояние будет равно n - |a - b|. Из

этих двух значений нужно выбрать наименьшее.

n = int ( input ( ) )

a = int ( input ( ) )

b = int ( input ( ) )

d = abs ( a - b )

print (min( d , n - d ) )

Задача 6. Речные прогулки

Набрать 60 баллов можно при помощи перебора по ответу. Переберём все пристани с номерами

от 2 до n - 1, и для каждой из них посчитаем разность между продолжительностью пути вверх и

вниз.

Пусть рассматриваемая пристань имеет номер x, тогда продолжительность пути до пристани 1

равна a(x - 1), а вниз - b(n - x). Нужно найти такую пристань x, для которой модуль разности

этих величин будет наименьшим.

Такое решение имеет сложность O(n). Пример такого решения.

n = int ( input ( ) )

a = int ( input ( ) )

b = int ( input ( ) )

def ans ( x ) :

return abs ( ( x - 1 ) ∗ a - ( n - x ) ∗ b )

d = 2

for i in range ( 3 , n ) :

i f ans ( i ) < ans ( d ) :

d = i

print ( d )

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

чения a(x - 1) и b(n - x) будут близки. Приравняем их, откуда получим решение уравнения

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 7-8 классы

Москва, 15 декабря 2024

x = (bn + a)/(a + b). Это число было бы ответом, если задача решалась в действительных числах,

когда началом маршрутов может быть любая точка. Но мы рассматриваем только целочисленные

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

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

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

Такое решение имеет сложность O(1).

n = int ( input ( ) )

a = int ( input ( ) )

b = int ( input ( ) )

def ans ( pos ) :

return abs ( ( pos

- 1) ∗ a - ( n - pos ) ∗ b )

d = max( 2 ,

( b ∗ n + a ) //

( a + b ) )

i f d + 1 < n and ans ( d + 1 ) < ans ( d ) :

d += 1

print ( d )

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

Задача 7. Благоустройство

Задача решается при помощи «жадного алгоритма». Пусть x - координата очередной точки, в

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

Тогда если x - prev >= d, то посадим дерево в точку x, обновив значение prev = x.

d = int ( input ( ) )

n = int ( input ( ) )

prev = -d

for i in range ( n ) :

x = int ( input ( ) )

i f x - prev >= d :

print (x)

prev = x

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

Задача 1. Речные прогулки

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

0.5 секунд

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

256 мегабайт

Вдоль течения реки размещены n пристаней, пронумерованных числами от 1 до n. Пристань

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

реки, расстояние между соседними пристанями равно 1 км.

Для развития туризма решено открыть два прогулочных речных маршрута. Маршруты будут

начинаться на одной из промежуточных пристаней (пристани номер 1 или n не могут быть началь-

ными точками маршрутов), один маршрут будет идти вверх по течению реки к пристани номер 1,

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

маршрутах нет.

Для подъёма вверх по течению реки судно тратит a минут на один километр, а для спуска вниз

по течению реки - b минут на один километр. Определите, на какой пристани должны начинать-

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

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

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

Первая строка входных данных содержит целое число n (3 :( n :( 2 · 10⁹) - общее количество

пристаней на маршруте. Вторая строка содержит число a - время подъёма судна на один километр

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

течению, 1 :( b < a :( 2 · 10⁹.

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

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

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

бой из них.

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

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

в 60 баллов.

Пример

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

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

Замечание

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

по течению судно поднимется за (3 - 1) × 7 = 14 минут, а вниз по течению реки спустится за

(8 - 3) × 3 = 15 минут. Разница в продолжительности маршрутов составит 1, меньшей разности в

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

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

Задача 2. Треугольники

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

0.5 секунд

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

256 мегабайт

Дана клетчатая сетка, состоящая из n × m клеток со стороной 1, в каждой клетке проведены

обе диагонали.

Например, сетка 1×2 выглядит следующим образом:

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

сетки, а длины его стороны равны 1 или 2 (то есть подходящими являются прямоугольники 1 × 1,

1 × 2, 2 × 1, 2 × 2).

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

сетки и он целиком лежит в каком-то подходящем прямоугольнике.

Посчитайте количество хороших треугольников на данной сетке.

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

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

сетки, 1 :( n :( 10⁸, 1 :( m :( 10⁸.

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

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

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

значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-

битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal,

тип long в Java и C#).

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

В данной задаче 20 тестов помимо тестов из условия, каждый из них оценивается в 5 баллов.

При этом в 4 тестах (помимо тестов из условия) n или m равно 1, в 4 других тестах n или m равно 2.

Примеры

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

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

196

Замечание

Все треугольники из первого примера:

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

Задача 3. Порядок во всём

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

2 секунды

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

256 мегабайт

Вася - очень порядочный мальчик, он любит порядок во всём.

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

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

поэтому единственное, что ему остаётся - это дописать цифры в конец некоторых чисел.

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

возможным. Найдите это число.

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

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

в тетрадке у Васи.

Следующие n строк содержат n чисел, записанных в тетрадке, по одному в каждой строке. Все

числа натуральные, не превосходящие 10⁹.

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

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

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

Решения, верно работающие, когда n :( 5 и при этом все числа в списке однозначные, будут

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

Решения, верно работающие, когда n :( 5 и при этом все числа в списке не превосходят 999,

будут оцениваться в 20 баллов.

Решения, верно работающие, когда n :( 5 без дополнительных ограничений на числа, будут

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

Решения, верно работающие, когда n :( 1000 без дополнительных ограничений на числа, будут

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

Примеры

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

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

100

Замечание

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

Во втором примере Васе можно приписать ко второму числу цифру 3, тогда числа станут рав-

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

последнее число.

В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие

варианты, но последнее число при любом способе дописывания цифр получится не меньше 100.

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

Задача 4. Тройка

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

2.5 секунд

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

256 мегабайт

Арсений очень любит пользоваться городским транспортом. В городе, где он живёт, существует

карта «Тройка», позволяющая оплачивать проезд при помощи тарифа «Кошелёк». Есть два вида

тарифа:

• «Единый» (57 рублей) - одна поездка на любом виде транспорта;

• «90 минут» (85 рублей) - не более одной поездки на метро и любое количество поездок на

наземном транспорте в течение не более 90 минут с момента начала первой поездки (между

началом поездки и началом первой поездки должно пройти не более 90 минут).

Так как Арсений коллекционирует карты «Тройка», у него их очень много, поэтому он может

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

У него есть планы на ближайшие n поездок. Помогите мальчику узнать, какое минимальное

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

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

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

запланированы, 1 :( n :( 10⁵.

Следующие n строк содержат два значения, разделённые пробелом. Сначала указан вид транс-

порта: заглавная английская буква «B», если Арсений будет использовать наземный транспорт, или

заглавная английская буква «M», если он воспользуется метро. Затем указано время начала поездки

в формате ЧЧ:ММ (в виде двузначного количества часов и затем двузначного количества минут).

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

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

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

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

Также гарантируется, что разница времени совершения двух поездок составляет не менее 10

минут.

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

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

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

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

Решения, правильно работающие при n :( 10, будут набирать не менее 10 баллов.

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

не менее 15 баллов.

Решения, правильно работающие, когда все поездки были совершены на наземном транспорте,

будут набирать не менее 25 баллов.

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

транспорте подряд, будут набирать не менее 35 баллов.

Решения, правильно работающие, когда все поездки были совершены в один день, будут набирать

не менее 25 баллов.

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

Примеры

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

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

M 10:00

B 10:20

B 11:00

142

B 23:59

M 00:29

M 00:59

B 01:29

142

B 22:00

B 23:00

B 23:50

B 00:30

Замечание

В первом примере все три поездки могут быть оплачены одним тарифом «90 минут» за 85 рублей.

Во втором примере нужно однимбилетом «90 минут» за 85 рублей оплатить первую (23:59), вто-

рую (00:29) и четвёртую (01:29) поездки. Третью поездку (00:59) нельзя оплатить тем же билетом,

потому что в тарифе «90 минут» может быть не более одной поездки на метро, для этой поездки

придётся использовать отдельный билет за 57 рублей.

В третьем примере первую поездку (22:00) нужно оплатить отдельным билетом за 57 рублей, а

следующие три поездки (23:00, 23:50, 00:30) - билетом «90 минут».

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

Задача 5. Все на съезд!

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

1.5 секунд

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

256 мегабайт

В 2025 году в Берляндии впервые будет проводиться трёхдневный межпланетный съезд по во-

просам проведения олимпиад по информатике. Доклады съезда разбиты на 12 секций, и теперь

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

ции.

Известно, что в съезде примут участие n человек. Каждый участник съезда выбрал 3 секции,

которые он хочет посетить. Но поскольку в один день секции будут проводиться одновременно,

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

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

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

сможет посетить их все.

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

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

больше. Помогите оргкомитету составить такое расписание.

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

Первая строка входных данных содержит целое число n (1 :( n :( 10000) - количество участни-

ков съезда.

В каждой из следующих n строк даны 3 попарно различных натуральных числа, не превосхо-

дящие 12, - номера секций, которые хочет посетить один из участников.

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

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

номера секций, проводимых в первый, второй и третий день съезда соответственно. Каждое из чисел

от 1 до 12 должно встречаться в выводе ровно один раз. Если возможных оптимальных расписаний

несколько, можно вывести любое из них.

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

Решения, правильно работающие, когда n = 1, будут оцениваться в 10 баллов.

Решения, правильно работающие, когда n = 2, будут оцениваться в 20 баллов.

Решения, правильно работающие, когда n = 3, будут оцениваться в 20 баллов.

Решения, правильно работающие, когда n :( 100, будут оцениваться в 75 баллов.

Пример

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

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

1 11 6 12

5 6 1

10 5 7 8

6 7 9

9 2 3 4

1 9 7

Замечание

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

желаемые секции, а первый - две секции (5 и одну из секций 1, 6). Таким образом, суммарно будут

посещены 8 секций. Можно показать, что этот результат улучшить нельзя.

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

Разбор задач

В разработке задач принимали участие Елена Андреева, Алексей Дацковский, Денис Кириенко,

Сергей Князевский, Семён Кухаренко, Дмитрий Михалин, Александр Понкратов, Арсений Порху-

нов, Владимир Рагулин.

Задача 1. Речные прогулки

Автор задачи: Денис Кириенко.

Набрать 60 баллов можно при помощи перебора по ответу. Переберём все пристани с номерами

от 2 до n - 1, и для каждой из них посчитаем разность между продолжительностью пути вверх и

вниз.

Пусть рассматриваемая пристань имеет номер x, тогда продолжительность пути до пристани 1

равна a(x - 1), а вниз - b(n - x). Нужно найти такую пристань x, для которой модуль разности

этих величин будет наименьшим.

Такое решение имеет сложность O(n). Пример такого решения.

n = int ( input ( ) )

a = int ( input ( ) )

b = int ( input ( ) )

def ans ( x ) :

return abs ( ( x - 1 )

∗ a - ( n - x ) ∗ b )

d = 2

for i in range ( 3 , n ) :

i f ans ( i ) < ans ( d ) :

d = i

print ( d )

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

чения a(x - 1) и b(n - x) будут близки. Приравняем их, откуда получим решение уравнения

x = (bn + a)/(a + b). Это число было бы ответом, если задача решалась в действительных числах,

когда началом маршрутов может быть любая точка. Но мы рассматриваем только целочисленные

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

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

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

Такое решение имеет сложность O(1).

n = int ( input ( ) )

a = int ( input ( ) )

b = int ( input ( ) )

def ans ( pos ) :

return abs ( ( pos - 1 )

∗ a - ( n - pos ) ∗ b )

d = max( 2 ,

( b ∗ n + a ) // ( a + b ) )

i f d + 1 < n and ans ( d + 1 ) < ans ( d ) :

d += 1

print ( d )

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

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

Задача 2. Треугольники

Автор задачи: Владимир Рагулин.

Подготовка задачи: Александр Понкратов.

Внутри каждого квадрата 1 × 1 можно выбрать 8 маленьких треугольников, как в первом при-

мере, то есть число таких треугольников равно 8nm.

Внутри прямоугольника 1 × 2 есть 2 больших треугольника площади 1. Прямоугольник 1 × 2

можно выбрать n(m - 1) способами, поэтому таких треугольников будет 2n(m - 1).

Аналогично, существует 2(n - 1)m больших треугольников, расположенных внутри какого-то

прямоугольника размером 2 × 1.

Наконец, внутри квадрата 2×2 можно выбрать 4 треугольника площади 2, таких треугольников

будет 4(n - 1)(m - 1).

Нужно вывести сумму этих величин.

n = int ( input ( ) )

m = int ( input ( ) )

print ( n ∗ m ∗ 8 + (n - 1) ∗ m ∗ 2 + n ∗ (m - 1) ∗ 2 + (n - 1) ∗ (m - 1) ∗ 4)

Задача 3. Порядок во всём

Автор задачи: Сергей Князевский.

Подготовка задачи: Владимир Ильин.

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

задача сводится к необходимости реализовать один шаг: даны два числа A и B, необходимо из

числа B дописыванием цифр в конец получить наименьшее число C, которое не меньше A.

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

Если длина числа B больше, чем длина числа A, то B > A и дописывать ничего не нужно.

Если длина числа B не больше длины числа A, то рассмотрим префикс A^lчисла A, длина

которого равна длине числа B. Например, если A = 1357, а число B - двузначное, то A^l= 13.

Поскольку числа A^lи B имеют одинаковую длину, то их можно сравнивать в лексикографическом

порядке, как строки. Рассмотрим разные варианты сравнения чисел A^lи B.

Если A^l= B, то число B является префиксом A, тогда мы можем дописать в конец B цифры

так, что получится число A, то есть C = A. Например, при A = 1357 и B = 13 значение C = 1357.

Если A^l> B (префикс A больше B), то при дописывании в конец числа B новых цифр мы

можем получить большее число, только когда длина числа C станет больше длины числа A. Тогда

необходимо дописать минимальное число нулей, чтобы длина числа C стала на 1 больше длины

числа A. Например, при A = 1357 и B = 12 значение C = 12000.

Наконец, если A^l< B, то нужно дописать нули так, чтобы длины чисел A и C стали равны.

Например, при A = 1357 и B = 14 значение C = 1400.

Пример решения на языке Python.

n = int ( input ( ) )

A = input ()

for i in range ( n - 1 ) :

B = input ( )

i f len (A) >= len (B) :

Ap = A [ : len (B) ]

i f Ap == B:

# Первый случай , дополним число B до A

C = A

e l i f Ap > B:

# Второй случай , дополним B нулями с увеличением длины числа

C = B + "0" ∗ ( len (A) + 1 - len (B) )

else :

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

# Третий случай , дополним B нулями до длины числа A

C = B + "0" ∗ ( len (A) - len (B) )

else :

# Длина числа B больше длины A, поэтому ниче г о добавлять не надо

C = B

A = C

print (A)

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

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

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

9999

9998

9997

9996

9995

то получатся следующие числа:

9999

99980

999700

9996000

99950000

Несложно построить тест, на котором такое решение имеет сложность O(n²). Такие решения

набирают 60 баллов.

Для того, чтобы набрать 100 баллов, необходимо заметить, что длины чисел увеличиваются за

счёт добавления нулей в конец, и сложность O(n²) возникает из-за того, что мы создаём строки

увеличивающейся длины, добавляя нули в конец чисел. Большую часть ответа в этом случае со-

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

префикс и количество нулей, которое нужно дописать в конец, в переменной zero_suff_len. Такое

решение имеет сложность O(n) и набирает 100 баллов.

n = int ( input ( ) )

A = input ( )

zero_suff_len = 0

for i in range ( n - 1 ) :

B = input ( )

i f len (A) + zero_ suff_ l en >= len (B) :

# Случай ко г да длина A <= длина B, но с учëтом дополнительно г о

# нулево г о суффикса . Для построения префикса A такой же длины ,

# как B, будем добавлять в конец A нули из суффикса

while len (A) < len (B) :

A += "0 "

zero_ suff_ l en -= 1

Ap = A [ : len (B) ]

# Последующий разбор случаев дублирует не эффективное решение

i f Ap == B:

C = A

e l i f Ap > B:

C = B

zero_ suff_ l en = zero_ suff_ l en + len (A) + 1 - len (B)

else :

C = B

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

zero_ suff_ l en = zero_ suff_ l en + len (A) - len (B)

else :

# Длина B больше , поэтому C = B и нужно с бросить zero_ suff_ l en

C = B

zero_ suff_ l en = 0

A = C

print (A + "0" ∗ zero_suff_ l en )

Задача 4. Тройка

Автор задачи: Денис Кириенко.

Подготовка задачи: Арсений Порхунов.

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

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

программа, выводящая число 57 ∗ n, наберёт 15 баллов.

Отметим «жадное» решение, в котором используется только одна карта «Тройка», а все списания

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

когда пассажир каждый раз при оплате проезда использует одну и ту же карту «Тройка». Для

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

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

решение набирает 30 баллов. Пример решения.

n = int ( input ( ) )

subway = [ 1 ] ∗ ( n + 1 )

time = [ -1000] ∗ ( n + 1 )

day = 0

for i in range ( 1 , n + 1 ) :

trans , tm = input ( ) . s p l i t ( )

tm = tm . s p l i t ( " : " )

time [ i ] = int ( tm [ 0 ] )

∗ 60 + int (tm [ 1 ] ) + day ∗ 24 ∗ 60

subway [ i ] = int ( t r a n s ==

"M" )

i f i > 0 and time [ i ] <= time [ i - 1 ] :

day += 1

time [ i ] += 24 ∗ 60

ans = [ 1 0 ∗ ∗ 9 ] ∗ ( n + 1)

ans [ 0 ] = 0

t i c k e t _ s t a r t = -10∗∗9

t i cket_ count = 0

ticket_count_subway = 0

for i in range ( 1 , n + 1 ) :

i f time [ i ] - t i c k e t _ s t a r t > 90 or ticket_count_subway + subway [ i ] > 1 :

ans [ i ] = ans [ i - 1 ] + 57

t i c k e t _ s t a r t = time [ i ]

t i cket_ count = 1

ticket_count_subway = subway [ i ]

else :

i f t i cket_ count ==

1 :

ans [ i ] = ans [ i - 1 ] + 28

else :

ans [ i ] = ans [ i - 1 ]

t i cket_ coun t

+= 1

ticket_count_subway += subway [ i ]

print ( ans [ - 1 ] )

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

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

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

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

совершена на метро (число 0 или 1). Дальше опустим эту часть программы.

Рассмотренное «жадное» решение не работает, например, на третьем примере из условия, где

даны 4 поездки: 22:00, 23:00, 23:50, 00:30. Это решение разобьёт их на группы (22:00, 23:00) и (23:50,

00:30), что потребует двух тарифов «90 минут», а если разбить решения на группы (22:00) и (23:00,

23:50, 00:30), то получится тариф «единый» и «90 минут». Чтобы правильно разбивать решения

на группы, необходимо использовать идею динамического программирования. Пусть ans[i] - ответ

для первых i поездок, то есть минимальная стоимость оплаты первых i поездок. Переберём все

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

1. Новая поездка оплачивается по тарифу «единый». Тогда ans[ i ] = ans[i-1] + 57.

2. Новая поездка оплачивается по тарифу «90 минут». Переберём первую поездку по этому та-

рифу j. Должны выполняться условия time[ i ] - time[j] <= 90 и сумма чисел subway[i], ...,

subway[j] не больше 1. Тогда ответ равен ans[ i ] = ans[j-1]+85.

Из возможных способов получения ans[ i ] нужно выбрать наименьшее. Такое решение набирает

50 баллов. В частности, оно работает правильно, когда все поездки совершены на наземном транс-

порте.

ans = [ 1 0 ∗ ∗ 9 ] ∗ ( n + 1)

ans [ 0 ] = 0

for i in range ( 1 , n +

1 ) :

ans [ i ] = 57 + ans [ i - 1 ]

count_subway = subway [ i ]

j = i - 1

while j >= 1 and time [ i ] - time [ j ] <= 9 0 :

count_subway += subway [ j ]

i f count_subway > 1 :

break

ans [ i ] = min( ans [ i ] , ans [ j - 1 ] + 85 )

j -= 1

print ( ans [ - 1 ] )

Это решение предполагает, что никакие два использованных тарифа не «пересекаются» по вре-

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

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

показано, что, например, в случае четырёх поездок B, M, M, B выгодно использовать тариф «90 ми-

нут» для наземного транспорта и одной поездки на метро, и отдельный тариф «единый» для другой

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

что пересечения возможны, только если внутри одного тарифа «90 минут» использовать отдельные

билеты для совершения поездок на метро, чтобы соблюсти условия одного тарифа «90 минут» для

поездок на наземном транспорте. А пересечения тарифов «90 минут» невозможны, то есть можно

построить лучшее решение, в котором использованные тарифы «90 минут» не будут пересекаться.

Чтобы учесть это в решении, введём новый вид тарифа «90 минут+», который допускает любое

число поездок на любом транспорте в течение 90 минут. Правила тарификации этого тарифа будут

такими: 85 рублей плюс 57 рублей за вторую и каждую последующую поездку на метро. Правиль-

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

решении, с тарификацией последней группы поездок с номерами от j до i по правилам тарифа

«90 минут+».

ans = [ 1 0 ∗ ∗ 9 ] ∗ ( n + 1)

ans [ 0 ] = 0

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

for i in range ( 1 , n +

1 ) :

ans [ i ] = 57 + ans [ i - 1 ]

count_subway = subway [ i ]

j = i - 1

while j >= 1 and time [ i ] - time [ j ] <= 9 0 :

count_subway += subway [ j ]

p r i c e = 85 + max( 0 , count_subway - 1 )

∗ 57

ans [ i ] = min( ans [ i ] , ans [ j - 1 ] + p r i c e )

j -= 1

print ( ans [ - 1 ] )

Задача 5. Все на съезд!

Автор задачи: Елена Андреева.

Подготовка задачи: Семён Кухаренко.

При n = 1 достаточно поставить желаемые секции единственного слушателя в разные дни.

При n = 2 также можно полностью удовлетворить обоих участников. Для этого разнесём в

разные дни секции первого участника, а потом ещё не распределённые секции второго поставим

так, чтобы он мог посетить все три.

При n = 3 всегда существует расписание, позволяющее двум участникам посетить все три же-

лаемые лекции, а третьему - две из трёх, при этом полностью удовлетворить всех трёх не всегда

возможно (это показано в примере из условия). Оптимальное расписание можно найти следую-

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

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

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

распределённые секции). Перебором случаев (различных распределений участников по секциям)

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

оптимальное решение.

Полное решение задачи заключается в переборе всех вариантов расписания. Такое решение мо-

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

При n

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

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

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

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

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

четыре секции. При этом мы переберём всего C⁴

· C⁴· C⁴= 34650 расписаний, для каждого из них

за O(n) посчитаем суммарное число посещений. Можно также заметить, что порядок следования

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

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

минимальным номером, стоящая не в первый день, стоит во второй день.

Это решение можно улучшить. Заметим, что количество различных пожеланий участников (т.е.

троек интересных секций) невелико (всего C³

= 12·11·10 3·2 = 220). Для каждой возможной тройки

секций a, b,c сохраним wishes[a][ b][c] - количество человек, желающих её посетить, и при про-

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

это число для тройки и умножать результат на значение wishes[a][ b][c]. Тогда ответ мы найдём

приблизительно за ³⁴⁶⁵⁰· 220 = 1270500 действий.

Ниже приведён код решения на языке Python с применением всех оптимизаций. В этом решении

используется нумерация с нуля как для секций, так и для дней.

wishes =

[ [ [ 0 for _ in range ( 1 2 ) ] for _ in range ( 1 2 ) ] for

_ in range ( 1 2 ) ]

ans = -1

# макс . число пос ещений

r e s = [ -1] ∗ 12

# оптимальное расписание

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

plan = [ -1] ∗ 12

# перебираемое расписание

cnt = [ 0 ] ∗ 3

# число уже поставленных с екций в к аждый д ень

def calc_ vis_ for_ part ( a , b , c ) : # считаем, сколько с екций из тройки можно

пос етить

i f plan [ a ] ==

plan [ b ] and plan [ b ] == plan [ c ] :

return

i f plan [ a ] ==

plan [ b ] or plan [ b ] == plan [ c ] or plan [ a ] == plan [ c ] :

return

def check ( ) :

# считаем сумма рное число пос ещений для plan

cnt = 0

for a in range ( 1 2 ) :

for b in range ( a + 1 ,

1 2 ) :

for c in range ( b + 1 ,

1 2 ) :

cnt += calc_ vis_ for_ part ( a , b , c )

∗ w ish es [ a ] [ b ] [ c ]

return cnt

# Рекурсивная функция перебора расписания

def gen ( i ) :

# i - номер с екции , которую будем распределять

global ans , res , cnt , plan

i f i ==

1 2 :

# расписание сформировано , выполняем проверку

nw = check ( )

i f nw > ans :

ans = nw

r e s = plan . copy ( )

return

for t in range ( 3 ) :

# проверяем, что мы не можем назначить с екцию в третий д ень

# е сли во второй д ень ещë не назначена ни одна с екция

i f t ==

2 and cnt [ 1 ] ==

0 :

break

i f cnt [ t ] < 4 :

# е сли в д ень t е сть свободные ме ста

cnt [ t ] += 1

# назначаем с екцию i в д ень t

plan [ i ] = t

gen ( i + 1 )

# вызываем рекурсивно алг оритм перебора

plan [ i ] = -1

cnt [ t ] -= 1

n = int ( input ( ) )

for _ in range ( n ) :

a , b , c = map( int , input ( ) . s p l i t ( ) )

# вычитаем 1 из номера с екции , чтобы перейти в ноль-нумерацию

# и упорядочиваем поже лания участника , чтобы a < b < c

a , b , c = sorted ( [ a - 1 , b - 1 , c - 1 ] )

wishes [ a ] [ b ] [ c ] += 1

# учитыв аем поже лания участника

# первую с екцию поставим в первый д ень

# везде используется ноль-нумерация

plan [ 0 ] = 0

cnt [ 0 ] = 1

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

Муниципальный этап всероссийской олимпиады школьников по информатике, 9-11 классы

Москва, 15 декабря 2024

gen ( 1 )

# выводим расписание

f = [ [ ] for _ in range ( 3 ) ]

for i in range ( 1 2 ) :

f [ r e s [ i ] ] . append ( i + 1 )

for i in range ( 3 ) :

for j in range ( 4 ) :

print ( f [ i ] [ j ] , end=’

’ )

print ( )

В приведённом выше решении используется рекурсивный алгоритм перебора расписания. Но по-

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

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

номера оставшихся трёх секций первого дня переберём тремя вложенными циклами. Из оставшихся

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

ции второго дня переберём вложенными циклами. Такое решение, вероятно, будет понятней для

начинающих.

n = int ( input ( ) )

# В словаре count считаем количе ство участников

# выбравших данную тройку с екций

count = dict ( )

for i in range ( n ) :

part = tuple ( sorted (map( int , input ( ) . s p l i t ( ) ) ) )

count [ part ] = count . get ( part ,

0 ) + 1

best_ count = 0

best_ans = [ ]

# d11 , d12 , d13 , d14 - номера с екций перво г о дня

d11 = 1

for d12 in range ( 2 ,

1 3 ) :

for d13 in range ( d12 + 1 , 1 3 ) :

for d14 in range ( d13 + 1 , 1 3 ) :

# day1 - список с екций дня 1

day1 = [ d11 , d12 , d13 , d14 ]

# day23 - список нераспределë нных с екций

day23 = [ i for i in range ( 2 ,

13 ) i f i not in day1 ]

# 0 , i 1 , i 2 , i 3 - индексы элементов из списка day23

# которые будут рас ставлены в д ень 2

for i 1 in range ( 1 , len ( day23 ) ) :

for i 2 in range ( i 1 + 1 , len ( day23 ) ) :

for i 3 in range ( i 2 + 1 , len ( day23 ) ) :

# day2 - список с екций дня 2

day2 = [ day23 [ 0 ] , day23 [ i 1 ] , day23 [ i 2 ] , day23 [ i 3 ] ]

# day3 - список с екций дня 3

day3 = [ i for i in range ( 2 ,

13 ) i f i not in

( day1 + day2 ) ]

curr_count = 0

# Перебираем вс е поже лания и считаем количе ство выполненных

for part in count :

for day in

( day1 , day2 , day3 ) :

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

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

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

Задача 1. Кузнечик 2D

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

1 секунда

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

512 мегабайт

В левом-нижнем углу прямоугольной клетчатой доски размером n × m стоит k-кузнечик. За

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

чем на k клеток.

Возможные ходы k-кузнечика для k = 3.

Необходимо передвинуть k-кузнечика в правый верхний угол доски в клетку (n, m). За какое

минимальное число ходов можно передвинуть k-кузнечика из клетки (1, 1) в клетку (n,m)?

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

В первой строке заданы три целых числа n, m и k - размеры сторон доски и максимальное

число клеток, на которое может ходить k-кузнечик, соответственно (1 :( n, m, k :( 10⁹).

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

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

из клетки (1, 1) в клетку (n, m).

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

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

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

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

Необходимые

Информация

Подзадача

Баллы

ограничения

подзадачи

о проверке

n, m :( 10, k = 1

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

n, m, k :( 10

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

n, m :( 10⁹, k = 1

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

Гарантируется, что ответ

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

равен 1 или 2

нет

1-4

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

Примеры

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

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

9 8 5

2 2 1

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

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

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

Задача 2. Простоватые числа

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

1 секунда

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

512 мегабайт

Назовём число простоватым, если произведение цифр этого числа в десятичной системе счисле-

ния является простым числом. Например, простоватым является число 12, а число 29 не является.

Требуется посчитать количество простоватых чисел от l до r, включительно.

Напомним, что целое число p > 1 называется простым, если оно имеет ровно два делителя: 1 и p.

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

Первая строка содержит одно целое число l (1 :( l :( 10¹⁰⁰⁰⁰⁰).

Вторая строка содержит одно целое число r (l :( r :( 10¹⁰⁰⁰⁰⁰).

Обратите внимание, что числа во вводе не помещаются в стандартные типы данных для це-

лых чисел в большинстве языков программирования, в частности, в C++. Необходимо каким-либо

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

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

Выведите количество простоватых чисел от l до r.

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

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

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

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

Необходимые

Информация

Подзадача

Баллы

ограничения

подзадачи

о проверке

1 :( l :( r :( 10⁶

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

1 :( l :( r :( 10¹⁸

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

l = 1, r = 10^k, где k

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

(1 :( k :( 10⁵)

1 :( l :( r :( 10¹⁰⁰⁰

1, 2

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

1-4

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

Пример

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

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

179

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

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

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

Задача 3. Кислотные дожди

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

1 секунда

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

512 мегабайт

Для сборки лаборатории-поселения на Венеру доставлены n блоков. Блоки расположены в ряд,

i-й блок имеет высоту h_i.

Сборку будет осуществлять специальный робот. В процессе сборки последовательные сегменты

блоков будут постепенно объединяться. При этом порядок блоков в ряду не будет меняться.

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

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

из блоков A = [i, i + 1, . . . , i + p - 1] и сегмент из блоков B = [i + p, i + p + 1, . . . , i + p + q - 1], то после

их объединения в один получается сегмент AB = [i, i + 1, . . . , i + p - 1, i + p, i + p + 1, . . . , i + p + q - 1].

Инструкция по сборке состоит из n- 1 инструкций. Каждая инструкция характеризуется одним

числом, j-я инструкция характеризуется числом k_j. После выполнения этой инструкции сегменты с

номерами k_jи k_j+1 объединяются в один, получившийся сегмент занимает место в последователь-

ности сегментов на месте двух объединенных сегментов, и вводится новая нумерация на сегментах

в том порядке, в котором они расположены - номера сегментов, начиная с k_j+ 2, уменьшаются на

один. После выполнения всех инструкций все сегменты окажутся объединены в один общий сегмент.

НаВенере постоянно идут кислотные дожди, поэтому в процессе сборкиважно для каждого сег-

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

из блоков высотой h_l, hl+1, . . . , h_r. Для p, где l :( p :( r определим глубину блока c высотой h_pв этом

сегменте следующим образом. Посчитаем величины l_p= max{h_l, . . . , h_p}, r_p= max{h_p, . . . , h_r}. Это

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

d_p= min(l_p, r_p) - h_p, заметим, что d_p

0. Емкостью сегмента будем называть сумму глубин блоков

этого сегмента, то есть w = d_l+ dl+1 + . . . + d_r.

Задана последовательность объединений сегментов. После каждого объединения выведите ем-

кость получившегося сегмента.

Рисунок на следующей странице показывает процесс выполнения инструкции из примера, над

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

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

Первая строка содержит одно целое число n - количество блоков (2 :( n :( 10⁵).

Во второй строке записано n чисел h₁, . . . , h_n(1 :( h_i:( 10⁹).

В третьей строке записаны n - 1 чисел - инструкции по объединению сегментов. Каждая ин-

струкция характеризуется одним числом k_j(1 :( k_j:( n -j).

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

Выведите n-1 чисел - после каждого объединения сегментов выведите емкость получившегося

объединенного сегмента.

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

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

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

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

Баллы за подзадачи 1 - 7 начисляются только в случае, если все тесты соответствующей подза-

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

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

Необходимые

Информация

Подзадача

Баллы

ограничения

подзадачи

о проверке

n :( 100

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

n :( 1000

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

h_i:( 10

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

Для некоторого i выполнено

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

h₁ . . .

h_i:( . . . :( h_n

Во всех запросах k_j= 1

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

n :( 4 · 10⁴

1, 2

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

нет

1-6

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

Пример

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

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

9 1 8 1 5 2 3 6

3 3 1 3 3 2 1

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

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

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

Задача 4. Поиск сокровищ

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

2 секунды

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

512 мегабайт

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

Представим область для поисков как таблицу из k строк и n столбцов. Нумерация строк идет от

1 до k сверху вниз, нумерация столбцов от 1 до n слева направо. В каждой клетке таблицы могут

находиться полезные ископаемые.

Сканер работает следующим образом: он может быть запущен в столбце p и возвращает коли-

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

включает все клетки столбца p, верхние k - 1 клетку столбца p - 1, верхние k - 2 клетки столбца

p-2, и так далее. На рисунке показана зона сканирования для поля с k = 3, n = 5 и всех значений p.

p=1

p=2

p=3

k=3

n=5

p=4

p=5

Вам даны значения, которые вернул сканер для всех p, обозначим за b_pзначение в столбце p.

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

паемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере

выше сканер вернул значения [2, 1, 2, 3, 2], то одна из корректных таблиц может выглядеть следую-

щим образом (клетки, содержащие ископаемые, обозначены черным треугольником):

p=1

p=2

p=3

k=3

n=5

p=4

p=5

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

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

сканер неисправен, и корректных таблиц вообще нет, тогда необходимо вывести 0.

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

Впервойстрокеданыдва числа n,k - количество столбцов и строк,соответственно(1 :( n :( 200,

1 :( k :( 7).

Во второй строке даны n чисел b₁,b₂,...,b_n- значения, которые вернул сканер (0 :( b_i:( k²).

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

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

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

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

Выведите единственное число - остаток от деления количества различных корректных таблиц

на 10⁹+ 7.

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

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

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

Необходимые

Информация

Подзадача

Баллы

Ограничения

подзадачи

о проверке

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

k :( 2

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

k :( 3

1, 2

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

k :( 4

1-3

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

k :( 5

1-4

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

k :( 6

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

1 :( n · k :( 25

Без дополнительных ограничений

1-6

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

Пример

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

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

5 3

2 1 2 3 2

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

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

Региональный этап, разбор задач

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

Региональный этап

Разбор задач

Условия задач, тесты, решения и разбор задач подготовили Александр Бабин, Николай Ведер-

ников, Екатерина Ведерникова, Никита Голиков, Мария Жогова, Владимир Рябчун, Маргарита

Саблина, Андрей Станкевич, Григорий Шовкопляс, Егор Юлин.

Ценные замечания по результатам тестирования задач сделали Тимур Дегтярев, Илья Кондаков,

Виталий Курин, Игорь Маркелов, Григорий Солнышкин, Максим Туревский, Максим Шевкопляс,

Ксения Шкулева.

Задача 1. Кузнечик 2D

Подзадача 1

Заметим, что при k = 1 любые два хода вверх и вправо можно заменить на один ход по диагонали.

Тогда до тех пор, пока кузнечик не дойдет до n-й строки или m-го ряда, будем двигать его по

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

10 можно реализовать такое

решение итеративно, используя цикл.

Асимптотика такого решения O(n + m).

Подзадача 2

Для решения данной подзадачи нужно модифицировать решение прошлой подзадачи для k > 1.

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

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

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

динаты после следующего хода по формулам: xⁱ= min(n, x + k), yⁱ= min(m, y + k).

Асимптотика такого решения O(n + m).

Подзадача 3

На самом деле для решения случая k = 1 можно не использовать цикл, а придумать формулу.

Максимальное число ходов по диагонали будет равно min(n, m)-1, а оставшихся ходов нужно будет

сделать max(n, m) - min(n, m). Итоговый ответ будет равен max(n, m) - 1.

Асимптотика такого решения O(1).

Подзадача 4

По условию данной подзадачи ответ всегда равен 1 или 2, поэтому в решении можно использо-

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

выведем 2.

Как понять, что можно переместить кузнечика за один ход? Заметим, что это значит, что либо

n = 1, либо m = 1, либо n = m, так как за один ход нам доступно только одно направление движения.

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

что можно сделать по формуле: max(n, m) - 1 k.

Асимптотика такого решения O(1).

Подзадача 5

Совместим идеи решения второй и третьей подзадач, а именно, используя алгоритм ходов из

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

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

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

Региональный этап, разбор задач

Максимальное число ходов по диагонали будет равно diagonal = lmin(n,m)-1l, а оставшихся

ходов нужно будет сделать rest = lmax(n,m)-min(n,m) l. Итоговый ответ будет равен diagonal + rest.

Асимптотика такого решения O(1).

Задача 2. Простоватые числа

Подзадача 1

Переберем все числа от l до r и каждое проверим, является ли оно простоватым или нет.

Подзадача 2

Заметим, что простоватые числа имеют вид: все цифры, кроме одной - единицы, а эта цифра -

2, 3, 5 или 7.

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

диапазон от l до r.

Подзадача 3

Количество чисел длины d равно 4·d, так как на каждую из d можем поставить одну из четырех

цифр.

),_k

Тогда количество чисел длиной от 1 до k равно

= 4 · d = 4 · d · (d + 1)2 = 2 · d · (d + 1).

d=1

Подзадача 4

Чтобы найти количество чисел на отрезке от l до r, найдём количество чисел от 1 до r и вычтем

количество чисел от 1 до l - 1.

Пусть мы хотим подсчитать количество чисел от 1 до s.

Для начала добавим к ответу все числа длины меньше len(s), что мы умеем решать в подзадаче

Осталось понять, сколько чисел длины len(s) будут подходить. Для этого надо перебрать пози-

цию i и проверять, можем ли мы поставить цифры 2, 3, 5 и 7. То есть формировать строки вида

1 . . . 1p1 . . . 1, где p - 2, 3, 5 или 7. И сравнивать с s. Сколько строк меньше, столько и добавим к

ответу. Такое решение будет работать за O(n²), так как строк кандидатов у нас 4 · n и сравнение

двух строк за O(n).

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

Оптимизируем последний шаг из решения подзадачи 4. Для этого можно заметить, что есть

несколько случаев, в которых мы не можем поставить цифру d на позицию i.

• Первые j цифр числа единицы, а s[j + 1] = 0, где s[j + 1] - цифра на j + 1 месте, и j + 1 < i.

• Первые i - 1 цифр числа единицы, а дальше s[i] < d.

• Первые i -1 цифр числа единицы, а дальше s[i] = d, а дальше идут несколько единиц подряд

и сразу после них ноль.

Во всех остальных случаях мы сможем поставить цифру d на позицию i. Такие проверки мы

можем осуществить во время прохода по строке s. Итоговое время работы будет O(n).

Задача 3. Кислотные дожди

Подзадачи 1 и 2

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

ответ по указанной формуле.

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

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

Региональный этап, разбор задач

Структуры данных

Во всех следующих подзадачах необходимо эффективно поддерживать границы сегментов. Ав-

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

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

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

1 на суффиксе массива s.

Подзадача 4

Для решения подзадачи4 для вычисления ответа на сегменте [l;r] нужно было найти подотрезок

блоков [lⁱ; rⁱ], такой что l

),_r

rⁱ

r и ∀i ∈ [lⁱ; rⁱ] : h_i

min(h_l, h_r). Тогда ответ будет равен

(rⁱ- lⁱ+ 1) · min(h_l! , h_r! ) -

h_i. lⁱи rⁱможно находить при помощи двоичного поиска.

i=l^!

Важные формулы

Для решения остальных подзадач нужно модифицировать формулу для вычисления ответа.

Воспользуемся следующим свойством: min(a, b) = a + b - max(a, b).

w = d₁+ d₂+ . . . + d_n=

min(l_i, r_i) - h_i=

i=1

l_i+ r_i- max(l_i, r_i) - h_i

i=1

Важное наблюдение: max(l_i, r_i) = max{h₁, . . . , h_n}. Обозначим за M максимум в сегменте.

Итоговая формула будет иметь вид:

'\"

w =

l_i+ r_i- max(l_i, r_i) - h_i=

l_i+

r_i-

h_i- n · M

i=1

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

сумма обновляются тривиально. Осталось научиться вычислять

l_iи

r_i.

Подзадача 3

В подзадаче 3 количество различных значений l_iи r_iбыло достаточно маленьким. Значения l_i

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

вхождения каждого возможного числа(а их 10). Например, массиву [2,1, 1, 5, 2] будет соответство-

вать массив l = [2, 2, 2, 5, 5], а позиции первых значений будут [1, 0, -1, -1, 3, -1, . . .]. По нему легко

вычислить

l_iи

r_i.

Подзадача 5

Подзадача 5 позволяла значительно упростить объединения сегментов, поскольку блоки всегда

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

l_iтривиально. Пусть наш текущий сегмент

состоит из элементов h₁, . . . , h_n, а мы хотим добавить элемент x в конец. Тогда какой-то суффикс

значений r_iстанет равен x, а остальная часть не поменяется. Эффективно поддерживать эти значе-

ния можно при помощи стека максимумов. Значения на стеке будут убывать, самое верхнее будет

r_n= h_n. Храня на стеке значение r_iи длину отрезка этих элементов можно быстро обновлять сум-

му r_i. Каждый элемент будет помещён на стек ровно 1 раз, поэтому суммарная асимптотика будет

O(n).

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

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

Региональный этап, разбор задач

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

Для полного решения задачи нужно развить идею поддержания

r_iиз подзадачи 5 и научиться

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

шение предполагало использование двух деков, в подзадаче 6 можно было использовать std::set.

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

мещать элементы из меньшего сегмента в больший. Это гарантирует O(log n) перемещений любого

блока и итоговую асимптотику O(nlog n).

Задача 4. Поиск сокровищ

Подзадача 6

Для решения данной подзадачи можно было использовать перебор. Так как n ·k

25, то мы мо-

жем перебрать все доступные поля и проверить их на корректность. Это будет работать за O(2^nknk).

Подзадача 1

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

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

сканирования не пересекается. Тогда количество корректных таблиц будем считать с помощью дина-

мического программирования.Пересчет будет через предыдущую позицию. Мы знаем, какую сумму

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

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

работы будет равно O(n).

Подзадачи 2-3

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

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

перебирать, какие клетки будут заняты в текущем столбце, тогда размер динамики будет O(2k2n),

переход будет работать за O(2^k), а тогда итоговое время работы будет равно O(2k2+kn).

Подзадачи 4-5

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

что нам необходимо хранить не все клетки в предыдущих k столбцах. Пусть мы сейчас рассматрива-

ем позицию i, тогда нам нужны верхняя k -1 ячейка в столбце i-1, верхние k -2 ячейки в столбце

k · (k - 1)

ячеек. Для перехода в динамике так же будем

i-2 и так далее. Тогда необходимо хранить

k·(k-1)

перебирать расстановку ячеек в текущем столбце, тогда размер динамики будет равен O(2

n),

k·(k-1)

k·(k+1)

переход работает за O(2^k), а итоговое время работы равно O(2

n) или же O(2

n).

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

Для полного решения задачи заметим следующее: для пересчёта в подзадачах 4-5 мы использо-

вали только клетки в треугольнике, которые стоят на диагонали. В столбце i будет не более i клеток,

тогда будем хранить сумму в каждом столбце, всего таких состояний будет не более k!. Тогда пе-

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

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

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

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

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

маски диагонали треугольника. Время работы будет O(k!2^kn).

Задача 5. Разность квадратов

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

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

Региональный этап, разбор задач

Подзадача 1

Напишем функцию isSquare(x), которая будет проверять, является ли число x полным квад-

ратом целого числа.

Двумя вложенными циклами переберем все возможные пары чисел, проверим, являются ли эти

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

увеличим ответ на один. Время работы такого алгоритма O(r²).

Подзадача 2

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

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

чем

^√r, то итоговое время работы O(r^√r).

Подзадача 3

Теперь будем перебирать циклами только полные квадраты чисел. Каждый цикл будет работать

за

^√r. Тогда итоговое время работы O(^√r · ^√r) = O(r).

Подзадача 4

Применим ещё оптимизацию. Будем перебирать полные квадраты числа. Пусть a - полный

квадрат, тогда нам надо проверить, правда ли число a - d является полным квадратом, а так же

лежит в диапазоне от l до r. Такое решение будет работать за O(

(r)).

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

Рассмотрим уравнение x²- y²= d. Преобразуем (x - y)(x + y) = d. Получается, что x - y и

√

x + y делители числа d. Переберем делители числа d за O(

d) и проверим, что получившиеся x²и

y²удовлетворяют условию задачи.

Задача 6. Перекошенное разбиение

Подзадача 1

В первой подзадаче были ограничения n

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

перебором. В рекурсивной функции будем передавать текущую сумму на суффиксе, количество по-

дотрезков, а так же максимальную и минимальную сумму на подотрезках разбиения. При переходе

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

Получаем решение за O(2ⁿ).

Подзадача 2

Во второй подзадаче k = 2, поэтому достаточно перебрать префикс, который будет образовывать

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

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

всего массива минус сумма префикса.

Ключевая идея решения

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

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

максимальная сумма, находится левее отрезка, на котором достигается минимальная сумма (иначе

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

Заметим, что длина любого отрезка в таком разбиении не превышает n - k + 1. Рассмотрим

следующий процесс:

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

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

Региональный этап, разбор задач

1. Если длина отрезка с максимальной суммой равняется n - k + 1 - закончить процесс.

2. Иначе, если отрезок с максимальной суммой не является первым (префиксом), отобрать по-

следний элемент у предыдущего подотрезка разбиения и отдать его подотрезку с максимальной

суммой. В случае, если он был длины один, то разбить любой другой отрезок длины больше

чем один на два отрезка.

3. Иначе, если между отрезком с максимальной суммой и отрезком с минимальной суммой есть

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

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

элемент отрезку с максимальной суммой.

Заметим, что на каждом шаге такого процесса значение перекоса разбиения не уменьшается, и

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

и оптимальный ответ в итоге процесса будет одним из двух:

1. Максимальный отрезок имеет длину n - k + 1, а остальные отрезки длину один.

2. Максимальный отрезок является префиксом массива от 1 до i, а минимальный отрезок имеет

длину один и состоит из элемента на позиции i + 1.

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

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

лучший ответ.

Подзадача 3

В третьей подзадаче выполняется ограничение k = 3, поэтому легко разобрать первый случай:

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

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

суммы на каждом префиксе.

Подзадачи 4 - 5

В подзадачах 4 и 5 достаточно решить задачу за время O(n²). Для этого можно перебрать

отрезок длины n - k + 1 и наивно найти сумму на нем и минимум из остальных элементов. Так же

нужно разобрать второй случай: перебрать каждый префикс и обновить ответ.

Полное решение задачи

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

n-k +1 и минимум среди остальных элементов. Для этого предподсчитаем для массива префиксные

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

O(1) найти сумму на отрезке длины n - k + 1, минимум на префиксе и на суффиксе и обновить

ответ. Получаем решение задачи за линейное время.

Альтернативное решение с использованием динамического программирования

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

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

ной сумме подотрезка минус минимальной сумме подотрезка, с другой стороны, для максимизации

перекоса оптимально прибавить максимальную сумму и вычесть минимальную. Таким образом,

можно про перекос думать так: мы хотим прибавить одну из сумм на подотрезке и вычесть одну из

сумм на подотрезке разбиения.

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

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

Региональный этап, разбор задач

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

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

мальную сумму или нет, и вычитали мы уже минимальную сумму или нет. Тривиальная реализация

такого решения работает за время O(n²k), но можно оптимизировать это решение, получив решение

за O(nk).

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

Подзадача 1

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

о рюкзаке. Решим её за O(k₁· s).

Подзадача 2

Предсосчитаемdp₁[s] - всевозможныесуммыбаллов,которыеможнонабратьтолькоспомощью

первой задачи за O(k₁· s). Предсосчитаем dp₂[s] - все возможные суммы баллов, которые можно

набрать только с помощью второй задачи за O(k₂· s).

Теперь переберем 0 < x < s - сумма баллов по первой задаче. Тогда во второй надо набрать

s - x баллов. Если dp₁[x] = T rue и dp₂[s - x] = T rue, то можно набрать заданную сумму баллов.

Итоговая сложность: O(

k_i· s).

Подзадача 3

Напишем рекурсивный перебор за 2

k_i·

k_i. Будем для каждой задачи поддерживать количе-

ство выбранных подзадач и

Итоговая сложность: O(2

k_i).

Подзадача 4

Если все k_i= 1, а по условию мы должны взять хотя бы одну подгруппу из каждой задачи, то

в этой подзадаче мы обязаны взять все существующие подзадачи. А значит, достаточно проверить,

что

ci,1 = s.

Итоговая сложность: O(n).

Подзадача 5

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

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

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

Теперь нужно объединить полученные данные с предыдущими задачами. Это можно сделать за

m². Переберем доступные баллы в новой задаче s₁и доступные баллы в предыдущих s₂. Теперь мы

научились набирать s₁+ s₂, используя первые i + 1 задач.

Итоговая сложность: n · m².

Подзадача 6

Давайте посчитаем dp[i][j] - можно ли набрать первыми i задачами сумму ровно j.

Будем последовательно перебирать подзадачи задачи i. Пусть стоимость текущей подзадачи k,

и мы хотим её решить. Тогда в dp[i][j] можно прийти двумя способами.

1. Это первая решённая подзадача в данной задаче - сделаем переход из предыдущей задачи

dp[i - 1][j - k].

2. Это не первая решённая подзадача в данной задаче - сделаем переход из текущей задачи

dp[i][j - k].

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

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

Региональный этап, разбор задач

Чтобы правильно посчитать dp, необходимо перебирать j в порядке убывания.

k_i· s).

Итоговая сложность: O(

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

Введение

Ключевое значение в задаче играет следующий факт. Допустим, что цикл имеет длину 2n+2m-4

и проходит через клетки (1, 1) и (n, m), тогда при удалении этих клеток из цикла образуются два

пути. Один из этих путей соединяет клетки (1, 2) и (n - 1, m), другой путь соединяет клетки (2, 1)

и (n, m - 1), при этом сами пути не пересекаются.

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

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

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

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

Подзадача 1

Заметим, что при n = 3 существует только O(m²) интересных циклов. Это так, потому что верх-

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

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

каждую дугу на корректность за время O(m). Проверка на корректность включает в себя:

• Проверка на то, что дуги не пересекаются.

• Проверка на то, что дуги проходят через все отмеченные клетки (кроме, возможно, клеток

(1, 1) и (n, m), так как по нашему определению дуги через эти клетки не проходят, но при этом

понятно, что такие клетки все равно будут включены в любой рассматриваемый цикл).

Подзадачи 2-3

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

возможные пары дуг и проверить, что они формируют интересный цикл. С учетом n, m

8 для

каждой дуги можно было независимо перебрать маску переходов длины n+m-1 (каждый горизон-

тальный переход можно закодировать цифрой 0, а каждый вертикальный - цифрой 1). Требовалось

проверить следующие условия:

• Количество единиц в каждой из масок равняется n - 1.

• Дуги не пересекаются. Этот факт можно было проверить наивно, выписав все клетки верхней

и нижней дуги, а затем проверив всевозможные пары на совпадение.

• Каждая отмеченная клетка содержится в одной из двух дуг.

Без дополнительных оптимизаций такое решение с запасом работает при n, m

5. Для решения

подзадачи 3 требовалось оптимизировать этот перебор. Например, можно было поступить следую-

щим образом:

• Вычислить список возможных дуг, это можно сделать за O(2n+m-2), если перебрать все мас-

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

(₁₂)

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

= 924.

• Для каждого пути вычислить битовую маску клеток, которые посещает этот путь (поле содер-

жит не более чем 64 клетки, так что для хранения таких масок хватает беззнакового 64-битного

числа).

• Наивно перебрать всевозможные пары путей и проверить каждую из них за O(1).

(n+m-4)₂

Ясно, что перебор, организованный таким образом, работает за время O((n+m) 2n+m+

n-2

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

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

Региональный этап, разбор задач

Подзадачи 4-5

Для решения этих подзадач требовалось воспользоваться методом динамического программиро-

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

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

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

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

А именно предлагается вычислить массив dp[s][x₁][y₁][x₂][y₂] - количество пар непересекающих-

ся путей, первый из которых соединяет клетки (1, 2) и (x₁, y₁), а второй - клетки (2, 1) и (x₂, y₂).

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

которых выполняются x₁+ y₁= x₂+ y₂. Тогда переходы будут иметь вид:

dp[s][x₁][y₁][x₂][y₂] = dp[sⁱ][x₁-1][y₁][x₂-1][y₂] + dp[sⁱ][x₁-1][y₁][x₂][y₂-1]+

+ dp[sⁱ][x₁][y₁- 1][x₂- 1][y₂] + dp[sⁱ][x₁][y₁- 1][x₂][y₂- 1]

• Число s в состояниях динамики вычисляется в соответствии с его определением, таким образом

s - sⁱравняется количеству отмеченных клеток среди пары клеток (x₁, y₁) и (x₂, y₂).

Такое решение работает за O(kn²m²) и не является решением ни для одной из этих двух под-

групп. Для того, чтобы решить эти две подгруппы требовалось заметить следующие оптимизации:

• Заметить, что число y₂в состоянии лишнее, так как ненулевыми являются только те состояния

динамики, где выполнено x₁+ y₁= x₂+ y₂, таким образом всегда можно восстановить число

y₂.

• Число s также является лишним в состоянии динамики, так как требуется посетить все отме-

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

клетки можно распределить по диагоналям вида x + y = const. Теперь достаточно полагать

значения динамики dp[x₁][y₁][x₂] полагать равными нулю, если клетки (x₁, y₁) и (x₂, y₂) не

покрывают все отмеченные клетки на диагонали x₁+ y₁.

После озвученных оптимизаций мы получили решение, которое работает за время O(n²m).

Подзадача 6

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

торая предполагает линейное время работы программы в зависимости от n и m. Рассмотрим все-

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

n + m - 4

n + m -

n - 2

Отметим, что биномиальные коэффициенты легко вычислять за O(1), если предпосчитать массив

факториалов и обратных факториалов по модулю 10⁹+7. Но среди подсчитанных пар путей могли

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

их из ответа.

Утверждается, что количество таких путей равно:

n + m - 2

n + m -

n - 4

n - 1

(_n)

Примечание. Биномиальные коэффициенты вида

здесь полагаются равными 0, при k < 0

или k > n.

Действительно, рассмотрим любую пару пересекающихся путей P = P₁, . . . , Pn+m-3 и

Q = Q₁, . . . , Qn+m-3. Пусть k - минимальное число k, такое что C = P_k= Q_k. Тогда такой па-

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

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

Региональный этап, разбор задач

X = P₁, . . . , Pk-1, C, Qk+1, . . . , Qn+m-3

Y = Q₁, . . . , Qk-1, C, Pk+1, . . . , Pn+m-3

Заметим, что путь X соединяет клетки (1, 2) и (n, m - 1), а путь Y - клетки (2, 1) и (n - 1, m).

Любая такая пара путей гарантированно пересекается, то есть имеет общую клетку C. А это значит,

что для каждой такой пары можно точно также найти минимальный индекс k : X_k= Y_kи, выполнив

обратное преобразование, восстановить пару пересекающихся путей P и Q.

Иллюстрация описанной биекции в случае n = 3 и m = 4.

Только что мы построили биекцию между парами путей (X, Y ) и парами пересекающихся путей

(P, Q). Таким образом, размеры этих множеств совпадают, что доказывает предложенную ранее

формулу.

Пр(м)ча(ие)от автора задачи. Та же самая идея применяется в доказательстве соотношения

Cn =

, где C_n- n-е число Каталана, которое по определению равно количеству правиль-

n-1

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

в роли самостоятельной задачи на олимпиаде ВКОШП в 2022-м году.

Подзадача 7

Для решения этой подзадачи надо было осознать, как идея предыдущей подзадачи обобщается,

если есть ограничение на то, что нужно посетить какую-то клетку. Для удобства введем функцию

K(A, B), которая принимает на вход пару точек (A, B), а на выходе выдает количество путей,

которые начинаются в A и заканчиваются в B.

Для этой и последующих подзадач обозначим ключевые клетки: S₁= (2, 1), S₂= (1, 2),

T₁= (n, m - 1), T₂= (n - 1, m).

Пусть отмечена клетка L, тогда, если L совпадает с (1, 1) или (n, m), то она будет посещена

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

В ином случае, возможны два варианта, либо путь P : S₁→ T₁содержит клетку L, либо путь

Q: S₂→ T₂содержит L. Суммарное количество способов выбрать, на каком из путей будет лежать

клетка L, и какие именно это будут пути будет равно:

K(S₁, L) · K(L, T₁) · K(S₂, T₂) + K(S₂, L) · K(L, T₂) · K(S₁, T₁)

Проблемы у формулы в отличие от предыдущего случая уже две:

Страница 11 из 13

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

Региональный этап, разбор задач

• Учитываются пересекающиеся пары путей P и Q.

• Пути, которые пересекаются в клетке L, учитываются дважды.

Примечание В разборе подзадачи 10 будет указано, что никакого «нового» решения не требуется.

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

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

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

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

путей, их количество равно:

K(S₁, L) · K(L, T₁) · K(S₂, L) · K(L, T₂)

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

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

продолжают работать и при таком условии. Построенная биекция будет иметь вид:

• Пусть (P,Q) - пара путей, в которой один из путей содержит клетку L.

• Пусть k - минимальный индекс P_k= Q_k= C.

• Поменяем суффиксы путей, идущие после C, местами и получим пару путей (X,Y ).

• Заметим, что (X, Y ) это пара путей между клетками (S₁, T₂) и (S₂, T₁), в которой ровно один

из двух путей содержит клетку L.

Иллюстрация описанной биекции в случае n = m = 4 и L = (2,2).

Количество путей (X, Y ) вычисляется аналогично предыдущей подзадаче. Для того, что-

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

[P₁, . . . , P_k] = K(P₁, P₂) · . . . · K(Pk-1, P_k).

Таким образом, ответ на задачу равен:

ans = [S₁, L, T₁] · [S₂, T₂] + [S₁, T₁] · [S₂, L, T₂] - [S₁, K, T₁] · [S₂, K, T₂]-

-[S₁, L, T₂] · [S₂, T₁] - [S₁, T₂] · [S₂, L, T₁] + [S₁, K, T₂] · [S₂, K, T₁]

Страница 12 из 13

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

Региональный этап, разбор задач

Подзадача 8

Обобщим идею из решения предыдущей подзадачи. Пусть отмечены клетки L = {L₁, . . . , L_k},

заранее из этого списка вырежем клетки (1, 1), (n, m). Теперь за O(k · 2^k) для каждого B, подмно-

жества клеток L, вычислим K(S_i,B,T_j) - количество путей из S_iв T_j, которые проходят через все

клетки B.

Далее предлагается вычислить U (S_i, B, T_j) - количество путей S_i→ T_j, которые проходят че-

рез клетки из множества B, но не проходят через клетки из множества L\B. Это можно сделать

с помощью динамического программирования за время O(3^k) или за время O(k · 2^k) с помощью

преобразования мебиуса (обратное преобразование SOS-DP).

Тогда количество пар путей S₁→ T₁и S₂→ T₂, которые посещают все клетки L₁, . . . , L_k, и при

этом не пересекаются в этих клетках равно f(S₁, T₁, S₂, T₂) = _BU (S₁, B, T₁) · U (S₂, L\B, T₂).

Учитывая опыт решения предыдущей подзадачи, легко видеть, что ответ равен:

f(S₁, T₁,S₂, T₂) -f(S₁,T₂,S₂,T₁)

Подзадача 9

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

эту группу, но не проходит 10-ю. Эта подгруппа - некоторая гарантия того, что если участник

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

засчитано.

Подзадача 10

Пусть K(S, B, T ) - количество путей из S в T , которые проходят через множества клеток B.

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

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

'\"

K(S₁, B, T₁) · K(S₂, L\B, T₂)

K(S₁, B, T₂) · K(S₂, L\B, T₁)

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

пара путей может быть учтена какое-то количество раз. Заметим следующее:

• Каждой паре путей S₁→ T₂и S₂→ T₁, как и ранее, мы сопоставляем пару гарантированно

пересекающихся путей S₁→ T₁и S₂→ T₂. Таким образом, в первом и втором слагаемом

считаются пары путей S₁→ T₁и S₂→ T₂.

• Непересекающиеся пары путей S₁→ T₁и S₂→ T₂, которые проходят через все клетки из

множества L, учтены ровно 1 раз в первом слагаемом.

• Пары путей, которые пересекаются, в том числе пересекаются в k клетках из L в первом

слагаемом учтены 2^kраз, а во втором слагаемом - тоже 2^kраз, поэтому они не вносят ни

какого вклада в сумму.

То есть значение этого выражения - ответ на задачу. Давайте научимся вычислять это значение

за полиномиальное время.

Рассмотрим множество клеток E = {S₁, S₂, T₁, T₂} ∪ L и отсортируем клетки этого множества

(x, y) по возрастанию величины x + y, в итоге получив массив E₁, E₂, . . . , E_l.

Пусть S₁, S₂, T₁, T₂имеют индексы в массиве E, равные s₁, s₂, t₁, t₂, соответственно.

Положим, что dp[i][j] - равно количеству пар путей, которые начинаются в паре клеток (S₁,S₂),

и при этом проходят через все клетки E₁, E₂, . . . , E[max{i, j}]. При этом пара путей (P₁, P₂) будет

учитываться в этой сумме столько раз, сколько есть способов разбить клетки E₁, . . . , E[max{i, j}]

на пару множеств Y₁LJY₂, такую что путь P₁посещает все клетки Y₁, а путь P₂посещает все клетки

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

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

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

Задача 5. Разность квадратов

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

1 секунда

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

512 мегабайт

На доске были выписаны два квадрата натуральных чисел: x²и y², где l ::: y²< x²::: r. Числа

x²и y²стерли и выписали на доске их разность d.

По заданным l, r и d выясните, сколько различных пар натуральных чисел x², y²могло быть

выписано на доске.

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

В первой строке даны три числа d, l и r (1 ::: d ::: 10⁹, 1 ::: l ::: r ::: 10¹⁸).

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

Выведите количество подходящих пар квадратов.

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

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

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

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

Необходимые

Информация

Подзадача

Баллы

ограничения

подзадачи

о проверке

1 ::: d ::: 10³, 1 ::: l ::: r ::: 10³

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

1 ::: d ::: 10⁵, 1 ::: l ::: r ::: 10⁵

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

1 ::: d ::: 10⁷, 1 ::: l ::: r ::: 10⁷

1, 2

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

1 ::: d ::: 10⁹, 1 ::: l ::: r ::: 10¹⁰

1-3

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

1-4

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

Примеры

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

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

64 1 100

64 1 300

Замечание

В первом примере подходят числа 100 и 36. Во втором примере также подходят числа 289 и 225.

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

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

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

Задача 6. Перекошенное разбиение

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

1 секунда

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

512 мегабайт

Дан массив [a₁,a₂,. .. ,a_n], состоящий из неотрицательных целых чисел.

Рассмотрим разбиение массива на k непустых отрезков подряд идущих элементов. Назовем пере-

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

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

Например, если массив равен [2, 1, 3, 4], то у разбиения [2, 1, 3][4] перекос равен 6 - 4 = 2, у

разбиения [2, 1][3, 4] перекос равен 7 - 3 = 4, а у разбиения [2][1, 3, 4] перекос равен 8 - 2 = 6.

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

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

Первая строка содержит два целых числа n и k (2 ::: k ::: n ::: 300 000) длину массива и

количество подотрезков, соответственно.

Вторая строка содержит n целых чисел a_i(0 ::: a_i::: 10⁹) элементы массива.

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

Выведите одно число максимальный перекос разбиения данного массива на k отрезков.

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

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

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

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

Необходимые

Информация

Подзадача

Баллы

ограничения

подзадачи

о проверке

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

n ::: 15

k = 2

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

k = 3

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

n ::: 300

1, 4

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

n ::: 3 000

1-5

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

Примеры

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

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

4 2

2 1 3 4

5 4

2 1 3 4 1

Замечание

Первый пример разобран в условии задачи.

Во втором примере оптимальным разбиением является [2][1][3, 4][1]. Максимальная сумма на

подотрезках в данном разбиении равна 3 + 4 = 7, минимальная сумма равна 1, таким образом,

перекос равен 6.

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

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