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

 

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

 

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

    

 

   

 

    

 

содержание      ..      1       2         ..

 

 

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

 

 

Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 1. Построение наибольшего
Лука загадал Косте трёхзначное число. Об этом числе известно следующее:
• хотя бы две цифры числа делятся без остатка на 2;
• хотя бы две цифры числа меньше 6.
Помогите Косте: найдите наибольшее число, которое мог загадать Лука.
Страница 1 из 5
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 2. Коты и собаки
Для двух собак и трёх котов купили мячики: резиновый, пластиковый, деревянный, тряпичный,
меховой - каждого по два вида. Определите, какие мячики купили для каждого животного, если:
1. У каждого животного по два мячика разных видов.
2. Для Мурсии не покупали резиновый мячик.
3. Для одной из собак купили пластиковый и деревянный мячики.
4. Для Джульбарса купили резиновый и деревянный мячики.
5. Котангенс и Сникерс - родственники, а Вук и Мурсия - нет.
6. Мурсия - мама Котангенса.
7. Для Котангенса купили пластиковый мячик.
8. Для одного из котов купили тряпичный и резиновый мячик.
Запишите в ответе 10 строк, соответствующих тому, какому животному купили какой мячик. В
каждой строке должны быть две буквы. Первая буква - начальная буква клички животного (одна
из букв В , Д , К , М
, С ). Вторая буква - начальная буква материала (одна из букв д ,
м , п , р , т ). Например, следующая запись:
Вд
Дм
обозначает, что Вуку купили деревянный мячик, а Джульбарсу - меховой.
Страница 2 из 5
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 3. Баобаб
Саша очень любит большие деревья, а самое любимое его дерево - баобаб.
Сегодня на уроке информатики Саша узнал, что слова можно сравнивать в лексикографическом
(алфавитном) порядке, то есть слова тоже бывают маленькими (находящимися в начале словаря) и
большими (находящимися в конце словаря).
Напомним, что слова в словаре упорядочены по первой букве (то есть больше то слово, первая
буква которого стоит в алфавите позже), а при равенстве первых букв сравниваются вторые буквы,
при равенстве вторых букв - третьи и т.д. Например, из слов грейпфрут , лимон , манго и
мандарин лексикографически наибольшим будет слово мандарин , так как первые буквы слов
грейпфрут и лимон находятся в алфавите раньше первой буквы слова мандарин , а у слов
мандарин и манго совпадают первые три буквы ман , но четвёртая буква слова мандарин
стоит в алфавите позже, чем четвёртая буква слова манго .
Изучая лексикографический порядок слов, Саша написал на полоске бумаги слово БАОБАБ ,
разрезал полоску в двух местах и переставил три получившихся куска местами. Он хочет сделать
БАОБАБ ещё больше. Какое наибольшее слово в лексикографическом порядке он может полу-
чить?
Страница 3 из 5
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 4. Диалог нейросетей
Две нейросети ведут между собой диалог, по очереди записывая слова. Слова добавляются в
конец уже существующей строки без дополнительных пробелов. Каждая из программ знает только
четыре слова: push , pop , in и offtop , то есть в итоге получится строка, составленная только
из этих слов, без пробелов. Диалог будет считаться успешным, если выполнены следующие условия:
1. Первое и последнее слово этого диалога push .
2. В диалоге встречаются хотя бы по одному разу все четыре слова push , pop , in и offtop .
3. В диалоге нигде не встречаются следующие подстроки (то есть подряд идущие символы):
hinp , pinp , popp , npopo , hpopi , npu .
Например, диалог pushpopinofftoppush не будет успешным, так как в нём встречается под-
строка hpopi . Диалог pushinofftoppush не будет успешным, потому что в нём не использовано
слово pop . А диалог pushinofftoppop не будет успешным, потому что он не заканчивается словом
push .
Требуется найти успешный диалог, содержащий как можно меньше букв. В ответе запишите этот
диалог в виде строки, содержащей только буквы (без пробелов, запятых и иных разделителей). Ваш
ответ будет принят на проверку, только если он является успешным диалогом. Чем короче будет
ваш диалог, тем больше баллов вы получите.
Страница 4 из 5
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 5. Робот-пылесос
Современные роботы-пылесосы очень умные. Например, они способны в своей памяти строить
карту помещения, разбивать помещение на сектора и даже прогнозировать загрязнения каждого
сектора. Сектора, закрашенные в чёрный цвет, недоступны для уборки. Там, вероятно, стоит диван,
кресло или какое-то другое препятствие. Число на секторе - это прогнозируемое количество пыли.
У робота-пылесоса, который отмечен на карте помещения рисунком, заканчивается заряд батареи,
и пылесос может выполнить только X перемещений в соседний сектор. По какому маршруту лучше
пройти роботу, чтобы собрать как можно больше пыли?
Карта помещения
Робот-пылесос может передвигаться строго по свободным секторам (не покрашенным в чёрный
цвет) и не может выезжать за пределы помещения. Если пылесос сталкивается с препятствием или
стеной комнаты, то он останавливается.
Маршрут пылесоса необходимо записать в виде строки из символов U , D , L , R , где U
обозначает перемещение на один сектор вверх, D - перемещение вниз, L - перемещение влево,
R - перемещение вправо.
Например, при движении по маршруту URR робот-пылесос соберет 5 единиц пыли, а при
исполнении маршрута RRU соберёт 3 единицы пыли, затем столкнётся с препятствием и остано-
вится.
Запишите маршрут движения робота-пылесоса, при котором он сможет собрать наибольшее ко-
личество пыли при заданных X. Ответы записывайте в виде последовательностей символов U ,
D , L , R без пробелов и иных разделителей.
Значение X Маршрут
3
5
7
9
Страница 5 из 5
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Разбор задач
Максимальное количество баллов - 500
Задача 1. Построение наибольшего
Чтобы трёхзначное число было как можно большим, на первое место нужно поставить цифру 9.
Она нечётна и больше 6, поэтому для выполнения всех условий обе оставшиеся цифры должны быть
чётными и одновременно меньшими 6. Сама цифра 6 не подходит (она не меньше 6), цифра 5
- нечётна. А вот цифра 4 чётна и при этом меньше шести, поэтому на вторую и третью
позиции поставим её.
Ответ: 944.
Задача 2. Коты и собаки
В условии 4 написано, что Джульбарсу купили резиновый и деревянный мячи. Из условия 7
следует, что один из двух мячей Котангенса - пластиковый.
Из условий 5 и 6 получаем, что Мурсия, Котангенс и Сникерс - коты, а Джульбарс и Вук -
собаки.
В условии 3 сказано, что одной из собак купили пластиковый и деревянный мячики, значит, это
Вук.
В условии 8 сказано, что одному коту купили тряпичный и резиновый мячики, но это не могут
быть Котангенс (у него один мяч пластиковый) и Мурсия (из условия 2 ей не покупали резиновый
мячик). Значит, Сникерсу купили тряпичный и резиновый мячики.
Поскольку каждого мячика купили по два вида, то остались тряпичный и два меховых. Значит,
Мурсиидостались тряпичный имеховой, а Котангенсу - меховой и пластиковый (что мы установили
ранее).
Джульбарс: резиновый и деревянный.
Вук: пластиковый и деревянный.
Сникерс: резиновый и тряпичный.
Мурсия: тряпичный и меховой.
Котангенс: пластиковый и меховой.
Задача 3. Баобаб
Чтобы строка после разрезания и перестановки оказалась наибольшей в лексикографическом
порядке, необходимо на первое место поставить букву «O». Значит, буква «О» должна быть началом
одного куска, то есть разрез необходимо сделать перед буквой «О»: «БА-ОБАБ».
Помимо буквы «О», остались только буквы «А» и «Б». Нам нужно после буквы «О» поставить
как можно больше букв «Б». В слове «БАОБАБ» и так после буквы «О» идёт одна буква «Б», но
за ней идёт буква «А», поэтому сделаем второй разрез между «Б» и «А»: «БА-ОБ-АБ».
Теперь переставим куски так, чтобы после «ОБ» оказалась буква «Б»: «ОБ-БА-АБ».
Ответ: ОББААБ.
Задача 4. Диалог нейросетей
Заметим, что в условии есть запрет на следование «poppush» - оно содержит «popp» и запрет
на следование «inpush» - содержащее «npu». Отсюда следует, что окончание правильного диалога
всегда будет иметь вид «offtoppush». Ещё запрещено повторение «poppop».
Остальные запреты касаются следования трёх слов подряд: запрещены «pushinpush»,
«pushinpop», «popinpop», «popinpush», «offtopinpush», «offtopinpop», «inpopofftop», «pushpopin».
Рассмотрим начало «pushpop». После этого нельзя поставить «in» из-за запрета «hpopi», остаёт-
ся добавить «offtop» и получить «pushpopofftop». Далее нужно добавить «in» и выйти на окончание
«offtoppush», что даёт правильный диалог «pushpopofftopinofftoppush». Это один из самых коротких
диалогов, он содержит минимальное число слов - 6 - и имеет длину 25 символов. Но из-за повто-
рения длинного слова «offtop» - этот ответ не оптимален. Заметим, что «offtop» - единственное
повторённое слово этом варианте диалога.
Начало «pushofftop» заведомо не может быть лучше, так как в дальнейшем мы снова должны
будем использовать ещё одно вхождение «offtop» в окончании, а двойное вхождение «offtop» в ответ
мы уже обсудили.
Страница 1 из 6
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Теперь рассмотрим оптимальный вариант начала «pushin». Смысла добавлять далее «offtop» нет
по причине того, что далее его придется добавлять ещё раз для выхода, поэтому желательно здесь
поставить «pop». Напрямую этого делать нельзя из-за запрета «hinp». Но ничто не запрещает ещё
раз повторить короткое слово «in» и избавиться от этого запрета: «pushininpop». Но теперь нельзя
сразу добавить завершение «offtoppush» из-за запрета «npopo». Поэтому еще раз добавим слово
«in» и только потом - «offtoppush». Получим самый короткий диалог «pushininpopinofftoppush».
Он состоит из семи слов и имеет длину 23 символа.
Вот ещё варианты правильных диалогов из 25 символов: «pushofftoppopinofftoppush» и
«pushinofftoppopofftoppush» - они так же состоят из шести слов. Остальные правильные диало-
ги имеют длину не менее 27 символов.
Задача 5. Робот-пылесос
Решение основывается на переборе разных вариантов маршрутов, где мы стремимся набрать как
можно больше пыли.
Маршруты легче искать в такой таблице, если закрасить сектора в разные цвета в зависимости
от количества пыли. Это легко можно сделать в электронных таблицах: нужно переписать данные
в таблицу, выделить её и применить «Условное форматирование» -> «Цветовые шкалы» -> «Цве-
товая шкала зеленый-жёлтый-красный». Теперь маленькие числа будут красными, а большие -
зелёными. Такая таблица называется тепловой картой.
Тепловая карта помещения
Найдём решение для X = 3:
В радиусе трёх секторов от робота-пылесоса самые большие числа - это 5, 4 и несколько тро-
ек. Попытаемся их объединить и найти маршрут, который позволит роботу собрать наибольшее
количество пыли.
1. LLL 1+3+4=8
2. DRU 5+1+3=9
3. RDL 3+1+5=9
Остальные маршруты позволят собрать намного меньше пыли То есть наилучший маршрут
позволяет собрать 9 единиц пыли и будет иметь вид «DRU» или «RDL». Пример маршрута «RDL»:
Страница 2 из 6
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Для нахождения ответа при X = 5, 7, 9 используем аналогичную логику. Определяем области
секторов, где мы можем набрать больше всего пыли, и строим маршрут туда через сектора с наи-
большими числами.
Для X = 5 маршрут «LLLUU» позволяет собрать 14 единиц пыли.
Страница 3 из 6
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Для X = 7 маршрут «UULLLDD» позволяет собрать 20 единиц пыли.
Для X = 9 маршрут «DRRDRRRDD» позволяет собрать 27 единиц пыли.
Страница 4 из 6
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
Ещё один способ решения - написать программу, которая переберёт все маршруты нужной
длины и найдёт маршрут, позволяющий собрать больше всего пыли. Полный перебор можно ре-
ализовать через рекурсивный алгоритм поиска в глубину. Такое решение в данной задаче будет
работать довольно быстро, потому что маршрут максимальной длины не очень длинный.
x , y = 2 ,
3
# начальная координата робота
n , m = 7 , 9
# размеры помещения
# карта помещения. Препятствия заменены -99,
# чтобы роботу было явно невыг одно туда ходить
f i e l d = [ [ 3 ,
4 ,
1 ,
3 ,
-99,
3 ,
2 ,
1 ,
6 ] ,
[ 3 ,
-99,
1 ,
2 ,
1 ,
2 ,
2 ,
1 ,
1 ] ,
[ 4 ,
3 ,
1 ,
0 ,
3 ,
-99,
-99 ,
4 ,
3 ] ,
[ 1 ,
1 ,
-99,
5 ,
1 ,
2 ,
2 ,
2 ,
3 ] ,
[ 2 ,
3 ,
-99,
1 ,
-99 ,
2 ,
2 ,
4 ,
1 ] ,
[ 4 ,
1 ,
4 ,
1 ,
-99,
3 ,
3 ,
-99 ,
1 ] ,
[ 2 ,
3 ,
2 ,
2 ,
1 ,
4 ,
2 ,
-99,
9 ] ]
# двумерный список , г д е мы будем отме чать с ектора , по которым
# проехал робот-пыл е с о с . 0 - не проехал , 1 - проехал
used = [ [ 0 ]
∗ m for _ in range ( n ) ]
# из любо г о с ектора можно проехать в одну из четырëх сторон
( список направлений ) .
# 0 . y-1, x+0 - движе ние вверх (U)
# 1 . y+1, x+0 - движе ние вниз (D)
# 2 . y , x-1 - движе ние влево (L)
# 3 . y , x+1 - движе ние вправо (R)
d = [ [ - 1 ,
0 ] ,
[ 1 ,
0 ] ,
[ 0 ,
-1] ,
[ 0 ,
1 ] ]
# функция , которая проверяет, находится ли робот-пыл е с о с внутри помещения
def coord_ok ( i , j ) :
return
0 <= i < n and 0 <= j < m
# Функция рекурсивно г о перебора .
# i , j - текущая координата робота
# curEnergy - количе ство потраченно г о заряда
# cur Points - объ ëм с обранной пыли
# bp - путь , пройденный до текущей координаты
def d f s ( i , j , curEnergy , cur Points , bp ) :
# Если заряд закончился , заканчиваем движение
i f cur Energy ==
energy :
return cur Points , bp
maxPoints = 0
best Path = ""
# отправим робота на 4 разные стороны и посмотрим,
# откуда он прине с ет больше вс е г о пыли .
for k in range ( 4 ) :
i 1 = i + d [ k ] [ 0 ]
j 1 = j + d [ k ] [ 1 ]
i f coord_ok ( i 1 , j 1 ) :
x = f i e l d [ i 1 ] [ j 1 ]
f i e l d [ i 1 ] [ j 1 ] = 0
points , path = d f s ( i 1 , j 1 , cur Energy +1 , cur Points+x , bp+str ( k ) )
Страница 5 из 6
Пригласительный этап всероcсийской олимпиады по информатике для 4-5 классов
Образовательный центр «Сириус», 23-24 мая 2024
i f p o i n t s > maxPoints :
maxPoints = p o i n t s
best Path
= path
f i e l d [ i 1 ] [ j 1 ] = x
return maxPoints , best Path
# переберëм длины маршрутов и для кажд о г о случая найд ëм маршрут,
# который позволит роботу с обрать наибольше е количе ство пыли .
for i in
3 ,
5 ,
7 ,
9 :
energy = i
a , b = d f s ( x , y ,
0 ,
0 , "" )
# заменим номера направлений на буквы.
print ( b . r e p l a c e ( " 0 " , "U" ) . r e p l a c e ( " 1 " , "D" ) . r e p l a c e ( " 2 " , "L" ) . r e p l a c e ( " 3 " , "R" ) )
Страница 6 из 6
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 1. Почтовая марка
Команда дизайнеров работает над созданием макета почтовой марки с использованием нова-
торской квадратной перфорации. Подготовленное художником изображение имеет размеры w мил-
лиметров в ширину и h миллиметров в высоту (для удобства дальнейшей работы эти величины
выражаются нечётными натуральными числами). Рисунок печатается в типографии с белыми по-
лями шириной 2 миллиметра со всех сторон, после чего осуществляется перфорация, как показано
на рисунке.
По данным ширине w и высоте h изображения определите периметр получившейся почтовой
марки.
Ответом на эту задачу является некоторое выражение, которое может содержать целые числа,
переменные w и h (обозначаются английскими буквами), операции сложения (обозначаются +),
вычитания (обозначаются -), умножения (обозначаются *) и круглые скобки. Запись вида 2h для
обозначения произведения числа 2 и переменной h некорректна, нужно писать 2 * h.
Ваше выражение должно давать правильный ответ для любых нечётных натуральных значений
w и h. Например, для приведённых на первом рисунке w = 9 и h = 5 значение выражения должно
быть равно 76, а для приведённых на втором рисунке w = h = 3 значение выражения должно быть
равно 44.
Пример правильной формы записи ответа:
w * h - 2 * (h - 1)
Страница 1 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 2. Диалог нейросетей
Две нейросети ведут между собой диалог, по очереди записывая слова. Слова добавляются в
конец уже существующей строки без дополнительных пробелов. Каждая из программ знает только
четыре слова: «push», «pop», «in» и «offtop», то есть в итоге получится строка, составленная только
из этих слов, без пробелов. Диалог будет считаться успешным, если выполнены следующие условия:
1. Первое и последнее слово этого диалога «push».
2. В диалоге встречаются хотя бы по одному разу все четыре слова «push», «pop», «in» и «offtop».
3. В диалоге нигде не встречаются следующие подстроки (то есть подряд идущие символы):
«hinp», «pinp», «popp», «npopo», «hpopi», «npu».
Например, диалог «pushpopinofftoppush» не будет успешным, так как в нём встречается под-
строка «hpopi». Диалог «pushinofftoppush» не будет успешным, потому что в нём не использовано
слово «pop». А диалог «pushinofftoppop» не будет успешным, потому что он не заканчивается словом
«push».
Требуется найти успешный диалог, содержащий как можно меньше букв. В ответе запишите этот
диалог в виде строки, содержащей только буквы (без пробелов, запятых и иных разделителей). Ваш
ответ будет принят на проверку, только если он является успешным диалогом. Чем короче будет
ваш диалог, тем больше баллов вы получите.
Страница 2 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 3. Робот-пылесос
Современные роботы-пылесосы очень умные. Например, они способны в своей памяти строить
карту помещения, разбивать помещение на сектора и даже прогнозировать загрязнения каждого
сектора. Сектора, закрашенные в чёрный цвет, недоступны для уборки. Там, вероятно, стоит диван,
кресло или какое-то другое препятствие. Число на секторе - это прогнозируемое количество пыли.
У робота-пылесоса, который отмечен на карте помещения рисунком, заканчивается заряд батареи,
и пылесос может выполнить только X перемещений в соседний сектор. По какому маршруту лучше
пройти роботу, чтобы собрать как можно больше пыли?
Карта помещения
Робот-пылесос может передвигаться строго по свободным секторам (не покрашенным в чёрный
цвет) и не может выезжать за пределы помещения. Если пылесос сталкивается с препятствием или
стеной комнаты, то он останавливается.
Маршрут пылесоса необходимо записать в виде строки из символов «U», «D», «L», «R», где «U»
обозначает перемещение на один сектор вверх, «D» - перемещение вниз, «L» - перемещение влево,
«R» - перемещение вправо.
Например, при движении по маршруту «URR» робот-пылесос соберет 5 единиц пыли, а при
исполнении маршрута «RRU» соберёт 3 единицы пыли, затем столкнётся с препятствием и остано-
вится.
Запишите маршрут движения робота-пылесоса, при котором он сможет собрать наибольшее ко-
личество пыли при заданных X. Ответы записывайте в виде последовательностей символов «U»,
«D», «L», «R» без пробелов и иных разделителей.
Значение X Маршрут
3
5
7
9
Страница 3 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 4. День борьбы.
23 мая отмечается Международный день
спортивной борьбы.
Отрывной календарь
Поскольку соревнования по спортивному программированию часто проходит в остановке острой,
напряжённой и упорной борьбы, правительство Берляндии поручило национальной федерации этого
вида спорта организовывать и проводить все олимпиады по информатике в стране.
По мнению главы федерации, важнейшей характеристикой спортсмена (а теперь и программи-
ста) является его вес. Поэтому атлетов распределяют на весовые категории, соперники в которых
сравнительно равны по физическим возможностям.
Для первой олимпиады, проводимой под эгидой федерации, было принято решение разделить
всех 1000 участников всего лишь на три весовые категории (лёгкую, среднюю и тяжёлую).
На церемонии открытия олимпиады все программисты одной весовой категории выходят на
специальный помост для приветствия и фотографирования. Важнейшей характеристикой такого
помоста является прочность - он должен выдержать вес всех поднявшихся на него атлетов. По-
могите организаторам определить границы весовых категорий таким образом, чтобы наибольший
суммарный вес борцов из одной весовой категории был наименьшим.
Найдите такое подходящее разбиение участников по весовым категориям, чтобы суммы весов
первых A спортсменов (с наименьшим весом), следующих B спортсменов и последних C спортс-
менов (с наибольшим весом) из предложенного списка отличались как можно меньше. При этом
спортсмены с одинаковым весом должны находиться в одной весовой категории.
Входные данные для этой задачи находятся в файле электронной таблицы в виде неубывающего
списка натуральных чисел.
Скачать файл в формате Microsoft Excel.
Скачать файл в формате Libre Office Calc.
В качестве ответа запишите три числа A, B, C, дающие в сумме 1000. Баллы будут начисляться
только за такие ответы, в которых спортсмены с одинаковым весом целиком попадают в одну весо-
вую категорию. При этом чем меньше будет наибольший суммарный вес участников одной весовой
категории, тем больше баллов получит решение.
Замечание
Пример: в соревновании принимают участие 10 спортсменов и их веса равны 10, 20, 30, 30, 40,
40, 50, 50, 60, 100.
Назначим шесть первых программистов в лёгкую весовую категорию (их суммарный вес 170),
двух следующих - в среднюю (100), двух последних - в тяжёлую (160). Тогда помост должен
выдерживать вес 170. Такой же результат даст ещё одно разбиение: шесть первых спортсменов
назначить в лёгкую весовую категорию (170), трёх следующих - в среднюю (160), последнего -
в тяжёлую (100). Если пять первых программистов назначить в лёгкую весовую категорию (130),
трёх следующих - в среднюю (140), двух последних - в тяжёлую (160), то, на первый взгляд,
можно достигнуть ещё более оптимальной прочности помоста - 160. Но тогда пятый и шестой
участники (имеющие равный вес) окажутся в разных весовых категориях, что является нарушением
спортивного принципа.
Ответом в этом примере будут числа 6, 2, 2 или 6, 3, 1.
Страница 4 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 5. Обои и дипломы
Ограничение по времени:
0.5 секунд
Родители Андрея решили поклеить на одну из стен в его комнате новые обои. Высота стены -
n сантиметров, а ширина - m сантиметров. К сожалению, обои, выбранные родителями, Андрею
не понравились, и он решил их чем-нибудь закрыть. Так как он участвовал в большом количестве
олимпиад, у него накопилось много дипломов. Все дипломы у Андрея одинаковые - это прямо-
угольники высотой a сантиметров и шириной b сантиметров. Помогите Андрею узнать, сколько
квадратных сантиметров обоев он сможет завесить дипломами, если не будет их разрезать и пере-
ворачивать. Все дипломы должны целиком размещаться внутри стены и не накладываться друг на
друга.
Формат входных данных
В первой строке входных данных находится целое число n (1 n
2 · 109) - высота стены.
Во второй строке находится целое число m (1 m
2 · 109) - ширина стены.
В третьей строке находится целое число a (1 a
2 · 109) - высота диплома.
В четвёртой строке находится целое число b (1 b
2 · 109) - ширина диплома.
Формат выходных данных
Выведите одно целое число - площадь части стены, которая будет закрыта дипломами, если их
не поворачивать, не обрезать и не накладывать друг на друга.
Обратите внимание, что значение ответа в этой задаче может превышать возможное
значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-
битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в С и С++,
тип long в Java и С#).
Система оценки
Решения, правильно работающие при 1 n, m
104, будут оцениваться в 50 баллов.
Решения, правильно работающие при n < 2 · a и m < 2 · b, будут оцениваться в 15 баллов.
Пример
стандартный ввод
стандартный вывод
3
12
5
1
2
Замечание
В примере из условия можно разместить 6 дипломов, суммарная площадь которых равна 12
квадратным сантиметрам. Большее число дипломов разместить нельзя, они будут вылезать за гра-
ницы стены.
Страница 5 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 6. Светофор
Ограничение по времени:
0.5 секунд
Студент Павел недавно приобрёл себе подержанный автомобиль и теперь ездит на нём в универ-
ситет. На его пути в вуз имеется один загруженный перекрёсток, проезд через который регулируется
светофором. Сделав ряд поездок, Павел обнаружил интересную закономерность: пока на светофоре
горит зелёный свет, через перекрёсток успевает проехать не менее a, но не более b машин.
Сверху над перекрёстком установлена уличная видеокамера. Павел может подключиться к ней
со своего смартфона и сосчитать количество машин n, которые стоят перед светофором впереди
него (свою машину он тоже считает).
Назовём тактом светофора включение на нём зелёного сигнала. Напишите программу, опреде-
ляющую минимальный и максимальный номер такта, на котором Павел проедет перекрёсток.
Формат входных данных
В первых двух строках входных данных записаны целые числа a и b (1 a b
109). В третьей
строке записано целое число n (1 n
109).
Формат выходных данных
Выведите два целых числа - минимальный и максимальный номер такта светофора, на котором
Павел проедет перекрёсток.
Система оценки
Решения, правильно работающие при n
1000, будут оцениваться в 50 баллов.
Пример
стандартный ввод
стандартный вывод
3
2
5
4
10
Замечание
В примере из условия перед светофором стоят 10 машин. Если через перекрёсток будут проез-
жать по 5 машин на зелёный свет, то Павел проедет на втором такте. Если же будут проезжать по
3 машины, то он проедет лишь на четвёртом такте.
Страница 6 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 7. Робот
Ограничение по времени:
1 секунда
На бесконечной в обе стороны клетчатой полоске в клетке с нулевой координатой стоит робот.
Робот делает 1 шаг вправо, затем 2 шага влево, 3 шага вправо, 4 шага влево и так далее. Сделав
суммарно N шагов, робот останавливается. Определите координату клетки, в которой окажется
робот после остановки.
Формат входных данных
В единственной строке задано целое число N (0 N
1018).
Обратите внимание, что значения переменных в этой задаче могут превышать воз-
можные значения 32-битной целочисленной переменной, поэтому необходимо исполь-
зовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long
в C++, тип long в Java и C#).
Формат выходных данных
Выведите единственное число - координату клетки, в которой окажется робот после остановки.
Система оценки
Решения, правильно работающие при N
106, будут оцениваться в 30 баллов.
Решения, правильно работающие при N
109, будут оцениваться в 65 баллов.
Примеры
стандартный ввод
стандартный вывод
3
-1
6
2
Страница 7 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Разбор задач
Максимальное количество баллов - 500
Задача 1. Почтовая марка
Рассмотрим верхнюю линию периметра. Она состоит из горизонтальных линий общей длины
w + 4 и w + 1 вертикальных линий единичной длины. После упрощения получается следующее
выражение: 2 × w + 5.
Рассмотрев аналогично другие линии периметра получаем общую формулу 4 × w + 4 × h + 20.
Задача 2. Диалог нейросетей
Заметим, что в условии есть запрет на следование «poppush» - оно содержит «popp» и запрет
на следование «inpush» - содержащее «npu». Отсюда следует, что окончание правильного диалога
всегда будет иметь вид «offtoppush». Ещё запрещено повторение «poppop».
Остальные запреты касаются следования трёх слов подряд: запрещены «pushinpush»,
«pushinpop», «popinpop», «popinpush», «offtopinpush», «offtopinpop», «inpopofftop», «pushpopin».
Рассмотрим начало «pushpop». После этого нельзя поставить «in» из-за запрета «hpopi», остаёт-
ся добавить «offtop» и получить «pushpopofftop». Далее нужно добавить «in» и выйти на окончание
«offtoppush», что даёт правильный диалог «pushpopofftopinofftoppush». Это один из самых коротких
диалогов, он содержит минимальное число слов - 6 - и имеет длину 25 символов. Но из-за повто-
рения длинного слова «offtop» - этот ответ не оптимален. Заметим, что «offtop» - единственное
повторённое слово этом варианте диалога.
Начало «pushofftop» заведомо не может быть лучше, так как в дальнейшем мы снова должны
будем использовать ещё одно вхождение «offtop» в окончании, а двойное вхождение «offtop» в ответ
мы уже обсудили.
Теперь рассмотрим оптимальный вариант начала «pushin». Смысла добавлять далее «offtop» нет
по причине того, что далее его придется добавлять ещё раз для выхода, поэтому желательно здесь
поставить «pop». Напрямую этого делать нельзя из-за запрета «hinp». Но ничто не запрещает ещё
раз повторить короткое слово «in» и избавиться от этого запрета: «pushininpop». Но теперь нельзя
сразу добавить завершение «offtoppush» из-за запрета «npopo». Поэтому еще раз добавим слово
«in» и только потом - «offtoppush». Получим самый короткий диалог «pushininpopinofftoppush».
Он состоит из семи слов и имеет длину 23 символа.
Вот ещё варианты правильных диалогов из 25 символов: «pushofftoppopinofftoppush» и
«pushinofftoppopofftoppush» - они так же состоят из шести слов. Остальные правильные диало-
ги имеют длину не менее 27 символов.
Задача 3. Робот-пылесос
Решение основывается на переборе разных вариантов маршрутов, где мы стремимся набрать как
можно больше пыли.
Маршруты легче искать в такой таблице, если закрасить сектора в разные цвета в зависимости
от количества пыли. Это легко можно сделать в электронных таблицах: нужно переписать данные
в таблицу, выделить её и применить «Условное форматирование» -> «Цветовые шкалы» -> «Цве-
товая шкала зеленый-жёлтый-красный». Теперь маленькие числа будут красными, а большие -
зелёными. Такая таблица называется тепловой картой.
Страница 1 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Тепловая карта помещения
Найдём решение для X = 3:
В радиусе трёх секторов от робота-пылесоса самые большие числа - это 5, 4 и несколько тро-
ек. Попытаемся их объединить и найти маршрут, который позволит роботу собрать наибольшее
количество пыли.
1. LLL 1+3+4=8
2. DRU 5+1+3=9
3. RDL 3+1+5=9
Остальные маршруты позволят собрать намного меньше пыли То есть наилучший маршрут
позволяет собрать 9 единиц пыли и будет иметь вид «DRU» или «RDL». Пример маршрута «RDL»:
Страница 2 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Для нахождения ответа при X = 5, 7, 9 используем аналогичную логику. Определяем области
секторов, где мы можем набрать больше всего пыли, и строим маршрут туда через сектора с наи-
большими числами.
Для X = 5 маршрут «LLLUU» позволяет собрать 14 единиц пыли.
Для X = 7 маршрут «UULLLDD» позволяет собрать 20 единиц пыли.
Страница 3 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Для X = 9 маршрут «DRRDRRRDD» позволяет собрать 27 единиц пыли.
Ещё один способ решения - написать программу, которая переберёт все маршруты нужной
длины и найдёт маршрут, позволяющий собрать больше всего пыли. Полный перебор можно ре-
Страница 4 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
ализовать через рекурсивный алгоритм поиска в глубину. Такое решение в данной задаче будет
работать довольно быстро, потому что маршрут максимальной длины не очень длинный.
x , y = 2 ,
3
# начальная координата робота
n , m = 7 , 9
# размеры помещения
# карта помещения. Препятствия заменены -99,
# чтобы роботу было явно невыг одно туда ходить
f i e l d = [ [ 3 ,
4 ,
1 ,
3 ,
-99,
3 ,
2 ,
1 ,
6 ] ,
[ 3 ,
-99,
1 ,
2 ,
1 ,
2 ,
2 ,
1 ,
1 ] ,
[ 4 ,
3 ,
1 ,
0 ,
3 ,
-99,
-99 ,
4 ,
3 ] ,
[ 1 ,
1 ,
-99,
5 ,
1 ,
2 ,
2 ,
2 ,
3 ] ,
[ 2 ,
3 ,
-99,
1 ,
-99 ,
2 ,
2 ,
4 ,
1 ] ,
[ 4 ,
1 ,
4 ,
1 ,
-99,
3 ,
3 ,
-99 ,
1 ] ,
[ 2 ,
3 ,
2 ,
2 ,
1 ,
4 ,
2 ,
-99,
9 ] ]
# двумерный список , г д е мы будем отме чать с ектора , по которым
# проехал робот-пыл е с о с . 0 - не проехал , 1 - проехал
used = [ [ 0 ]
∗ m for _ in range ( n ) ]
# из любо г о с ектора можно проехать в одну из четырëх сторон
( список направлений ) .
# 0 . y-1, x+0 - движе ние вверх (U)
# 1 . y+1, x+0 - движе ние вниз (D)
# 2 . y , x-1 - движе ние влево (L)
# 3 . y , x+1 - движе ние вправо (R)
d = [ [ - 1 ,
0 ] ,
[ 1 ,
0 ] ,
[ 0 ,
-1] ,
[ 0 ,
1 ] ]
# функция , которая проверяет, находится ли робот-пыл е с о с внутри помещения
def coord_ok ( i , j ) :
return
0 <= i < n and 0 <= j < m
# Функция рекурсивно г о перебора .
# i , j - текущая координата робота
# curEnergy - количе ство потраченно г о заряда
# cur Points - объ ëм с обранной пыли
# bp - путь , пройденный до текущей координаты
def d f s ( i , j , curEnergy , cur Points , bp ) :
# Если заряд закончился , заканчиваем движение
i f cur Energy ==
energy :
return cur Points , bp
maxPoints = 0
best Path = ""
# отправим робота на 4 разные стороны и посмотрим,
# откуда он прине с ет больше вс е г о пыли .
for k in range ( 4 ) :
i 1 = i + d [ k ] [ 0 ]
j 1 = j + d [ k ] [ 1 ]
i f coord_ok ( i 1 , j 1 ) :
x = f i e l d [ i 1 ] [ j 1 ]
f i e l d [ i 1 ] [ j 1 ] = 0
points , path = d f s ( i 1 , j 1 , cur Energy +1 , cur Points+x , bp+str ( k ) )
i f p o i n t s > maxPoints :
maxPoints = p o i n t s
Страница 5 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
best Path
= path
f i e l d [ i 1 ] [ j 1 ] = x
return maxPoints , best Path
# переберëм длины маршрутов и для кажд о г о случая найд ëм маршрут,
# который позволит роботу с обрать наибольше е количе ство пыли .
for i in
3 ,
5 ,
7 ,
9 :
energy = i
a , b = d f s ( x , y ,
0 ,
0 , "" )
# заменим номера направлений на буквы.
print ( b . r e p l a c e ( " 0 " , "U" ) . r e p l a c e ( " 1 " , "D" ) . r e p l a c e ( " 2 " , "L" ) . r e p l a c e ( " 3 " , "R" ) )
Задача 4. День борьбы
Рассмотрим несколько способов решения задачи.
Сначала посчитаем сумму всех чисел, например, используя формулу =SUM(A1:A1000). Эта сум-
ма равна 74995. Значит, при оптимальном разбиении спортсменов на 3 группы, в каждой из трёх
весовых категорий сумма весов должна оказаться примерно равной 25000.
Для каждой строки посчитаем сумму чисел в блоке от начала списка до этой строки (включи-
тельно). Для этого запишем в ячейку B2 формулу =SUM($A$1:A1), затем эту формулу скопируем
в блок B1:B1000.
Аналогично для каждой строки посчитаем сумму чисел в блоке от конца списка до этой строки
(включительно). Для этого запишем в ячейку C1000 формулу =SUM($A$1000:A1000), затем эту
формулу скопируем в блок C1:C1000.
Попробуем найти в столбцах B и C значение, примерно равное 25000. В ячейке C685 находим
число 25676, значит 316 последних участников в списке с весами от 78 и выше составляют тяжёлую
весовую категорию с суммой весов, весьма близкой к оптимальной.
В столбце B есть два значения, близкие к искомому:
1) В ячейке B334 находим число 23058, значит, если первых 334 участников в списке с весами
до 72 включительно объединить в лёгкую категорию, то в средней категории суммарный вес соста-
вит 74995 - 25676 - 23058 = 26261. Это наибольшее число из трёх (23058, 25676 и 26261), и пока
это лучшая из найденных прочностей помоста. При этом в средней весовой категории окажется
1000 - 316 - 334 = 350 спортсменов.
2) В ячейке B398 находим число 27730, значит, участников с весами до 73 включительно можно
объединить в лёгкую категорию. Однако их суммарный вес (27730) хуже, чем 26261, найденный
нами в разборе предыдущего случая.
Перебором других близких вариантов можно убедиться, что это лучшее решение.
Ответ: 334, 350, 316.
Как можно было облегчить решение задачи?
С учётом того, что в списке много повторяющихся весов, можно сильно облегчить себе работу
(и сократить обрабатываемые данные), если понять, что все значения у спортсменов одного и того
же веса можно сложить в одно число - ведь их всё равно нельзя делить на части.
Создадим новый столбец с уникальными весами. Для этого скопируем столбец A в новое ме-
сто (например, в столбец D) и избавимся от повторов (в MS EXCEL это можно сделать кнопкой
«Удалить дубликаты» на вкладке «Данные». Останется всего 33 различных значений весов. Теперь
просуммируем значения с одинаковыми весами и расположим их в соседнем столбце. Это можно
сделать с помощью формулы =SUMIF($A:$A;D1;$A:$A), которую распространим на все соответ-
ствующие ячейки столбца E). Вот что должно получиться:
Страница 6 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
Объём работы сократился с 1000 строк до 33.
Но можно и не создавать набор уникальных весов, а просто заметить, что веса принимают
значения от 59 до 93. Давайте в некоторых ячейках запишем граничное значение массы спортсмена
в этой категории. Например, в ячейках D1:D3 запишем числа 1, 2, 3, соответствующие номерам
категорий, а в ячейках E1:E3 напишем максимальные значения массы спортсмена в этой категории.
Теперь числа в блоке B1:B1000 заполним формулой, определяющей для каждого спортсмена номер
категории: =IFS(A1<=$E$1;1;A1<=$E$2;2;A1<=$E$3;3)
Теперь в блоке F1:F3 посчитаем массу спортсменов соответствующей категории, например, при
помощи формулы =SUMIF($B$1:$B$1000;D1;$A$1:$A$1000). А в блоке E1:E3 посчитаем количество
спортсменов в этой категории, например, при помощи формулы =COUNTIF($B$1:$B$1000;D1).
Наконец, подберём такие граничные значения в блоке E1:E3, чтобы максимум в блоке F1:F3
оказался минимальным. Правильный ответ будет выглядеть так:
Также можно написать программу на любом языке программирования. С учётом небольшого
числа спортсменов (всего 1000) и большого числа повторяющихся весов, можно использовать пол-
ный перебор. Переберём все возможные количества спортсменов в лёгкой категории и для этого
количества переберём все возможные количества спортсменов в средней категории. Если при этом
числа на границах групп различны, определяем прочность помоста для каждой категории и выби-
раем из них наибольшее значение. Если это значение - наименьшее для всех найденных до этого
момента, запоминаем его и соответствующие «границы» категории.
f = open( " data . csv " ,
" r " )
Data = [ int ( x ) for x
in f ]
n = 1000
best_max = 10 ∗∗ 18
# Лучше е значение прочности помоста
for a in range ( n - 2 ) :
# Номер последне г о спортсмена в лë гкой кат.
for b in range ( a+1 , n- 1 ):
# Номер последне г о спортсмена в средней кат.
i f Data [ a ]
!= Data [ a +
1 ] and Data [ b ]
!= Data [ b +
1 ] :
x = sum( Data [ : a +
1 ] )
# Сумма ве с ов в
лë г кой кате г ории
y = sum( Data [ a + 1
: b + 1 ] )
# Сумма ве с ов в средней кате г ории
Страница 7 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
z = sum( Data [ b + 1
: ] )
# Сумма ве с ов в тяжë лой кате г ории
d = max( x , y , z )
# Прочно сть помо ста (максимум из сумм ве с ов )
i f d < best_ delta :
best_ delta = d
best_a
= a+1
# Кол-во спортсменов в ответе в лë гкой кат.
best_b = b-a
# Кол-во спортсменов в ответе в средней кат.
print ( best_a )
print ( best_b )
print ( n
- best_a - best_b )
Задача 5. Обои и дипломы
Чтобы заполнить как можно большую площадь стены дипломами, Андрею нужно выкладывать
их вплотную друг к другу, начиная с самого края стены, до тех пор, пока это возможно.
Для решения на 15 баллов Андрей может положить всего один диплом - ответом будет a · b.
Для решения на 50 баллов можно смоделировать размещение дипломов на стене - прибавлять
в переменную ширину диплома, пока она не превысит ширину стены, аналогично и с высотой.
Для полного решения необходимо вывести формулу. Чтобы закрыть стену дипломами полно-
стью, например, в ширину, нужно, чтобы ширина стены делилась на ширину диплома. Если же она
не делится, то остаток закрыть не получится. Таким образом, можно просто вычесть из размеров
стены остатки от деления высоты стены n на высоту диплома a и ширины стены m на ширину
диплома b и перемножить получившиеся результаты.
Пример решения на языке Python.
n = int ( input ( ) )
m = int ( input ( ) )
a = int ( input ( ) )
b = int ( input ( ) )
print ( ( n - n % a )
∗ (m - m % b ) )
Задача 6. Светофор
Минимальный номер такта, на котором машина проедет перекресток, можно найти как In/bl,
то есть частное с округлением вверх. Например, в Python частное с округлением вверх можно
вычислить по формуле (n + b - 1) // b. Наибольшее число тактов будет достигаться, когда за один
такт через перекрёсток проезжает минимальное число машин, то есть In/al.
Пример решения на языке Python.
a = int ( input ( ) )
b = int ( input ( ) )
n = int ( input ( ) )
print ( ( n + b - 1 ) // b )
print ( ( n + a - 1 ) // a )
Задача 7. Робот
В решении на 30 баллов можно просто промоделировать движение робота, делая по одному
шагу. В этом решении в переменной direction хранится значение +1 или -1, обозначающее измене-
ние координаты при очередном шаге. Это значение меняется на противоположное (умножается на
-1), когда количество шагов curr_steps, сделанных в данном направлении, станет равно величине
max_steps, которая после этого увеличивается на 1.
n = int ( input ( ) )
x = 0
d i r e c t i o n = 1
curr_ steps
= 0
Страница 8 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
max_steps = 1
for i in range ( n ) :
x += d i r e c t i o n
curr_segment += 1
i f curr_ steps
==
max_steps :
d i r e c t i o n ∗= -1
curr_ steps = 0
max_steps += 1
print ( x )
Чтобы улучшить это решение и набрать 65 баллов, будем моделировать перемещения не по одно-
му шагу, а сразу добавляя к текущей координате 1, затем вычитая 2, добавляя 3 и т.д. Одновременно
с этим будем считать количество оставшихся шагов, вычитая из значения n числа 1, 2, 3, пока значе-
ние n будет положительным. Поскольку на последнем отрезке может оказаться так, что мы сможем
сделать не ровно steps шагов (переменная steps будет принимать значения 1, 2, 3, ...), а меньше, т.к.
иначе n станет отрицательным, то будем вычитать не значение steps, а минимум из steps и n.
Пример решения на языке Python.
n = int ( input ( ) )
d i r e c t i o n = 1
s t e p s = 1
x = 0
while n > 0 :
x += min( steps , n ) ∗ d i r e c t i o n
n -= min( steps , n )
s t e p s += 1
d i r e c t i o n ∗= -1
print ( x )
Чтобы решить задачу на 100 баллов, необходимо быстро определить, сколько полных циклов из
1, 2, 3, ... шагов пройдёт робот. Пусть это значение равно p. Тогда нужно найти такое максимальное
целое p, что 1+2+...+p n. Эту сумму можно вычислить по формуле арифметической прогрессии:
1 + 2 + ... + p = p(p + 1)/2. Итого нам нужно найти такое максимальное целое p, что p(p + 1) 2n.
√
Вместо этого возьмём p =
2n, округлив вниз до целого. То есть мы возьмём такое целое p, что
p2
2n, но при этом может оказаться так, что p(p + 1) > 2n. Несложно понять, что мы можем
ошибиться не более, чем на 1, поэтому проверим, не возникла ли ошибка, и уменьшим значение p
при необходимости.
Если было выполнено p полных циклов, то робот сделал p(p + 1)/2 шагов, поэтому ему осталось
сделать ещё n - p(p + 1)/2 шагов. Дальнейшие случаи зависят от того, будет ли значение p чётным
или нечётным. После выполнения 1, 2, 3, 4, 5 и т.д. полных циклов координата робота будет равна
1, -1, 2, -2, 3 и т.д. То есть при нечётном p робот закончит цикл в клетке (p + 1)/2, а значение
n - p(p + 1)/2 нужно будет вычесть. При чётном p робот закончит цикл в клетке -p/2, а значение
n - p(p + 1)/2 нужно будет прибавить.
Пример решения на языке Python.
n = int ( input ( ) )
p = int ( ( 2 ∗ n) ∗∗ 0 . 5 )
i f p ∗ ( p + 1) > 2 ∗ n :
p -= 1
i f p % 2 == 1 :
x = ( p + 1 )
// 2
x -= n - p ∗ ( p + 1 ) // 2
else :
x = - p // 2
x += n - p ∗ ( p + 1) // 2
Страница 9 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 6-7 классов
Образовательный центр «Сириус», 23-24 мая 2024
print ( x )
Также можно первую часть решения (нахождение наибольшего p такого, что p(p + 1) 2n)
выполнить двоичным поиском. Пример такого решения.
n = int ( input ( ) )
l e f t
= 0
r i g h t = n
while r i g h t - l e f t > 1 :
mid = ( l e f t + r i g h t )
// 2
i f mid ∗ ( mid + 1) <= 2 ∗ n :
l e f t = mid
else :
r i g h t = mid
p = l e f t
i f p % 2 == 1 :
x = ( p + 1 )
// 2
x -= n - p
∗ ( p + 1) // 2
else :
x = - p //
2
x += n - p
∗ ( p + 1) // 2
print ( x )
Страница 10 из 10
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 1. Змейка
Имя входного файла:
стандартный ввод
Имя выходного файла:
стандартный вывод
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Успешно решив раньше времени контрольную работу по математике, Тимофей выбрал на клет-
чатой бумаге квадрат со стороной n клеток и стал заполнять его «змейкой» от левого верхнего угла
так, как показано на рисунке. Определите длину проведённых линий.
Формат входных данных
Единственная строка входных данных содержит натуральное число n (1 n
109).
Формат выходных данных
Выведите одно натуральное число - ответ на вопрос задачи.
Обратите внимание, что значение ответа в этой задаче может превышать возможное
значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-
битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++,
тип long в Java и C#).
Система оценки
Решения, правильно работающие при n
104, будут оцениваться в 40 баллов.
Примеры
стандартный ввод
стандартный вывод
1
3
5
35
Страница 1 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 2. Две сестры
Имя входного файла:
стандартный ввод
Имя выходного файла:
стандартный вывод
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Аполлинария Прокофьевна и Белла Прокофьевна - две сестры-пенсионерки. Аполлинарии Про-
кофьевне каждый день необходимо принимать одну таблетку от забывчивости. К сожалению, этот
режим она не соблюдает и вспоминает о лекарстве только раз в a дней (то есть приняв лекарство
сначала в первый день, в следующий раз она примет его в день номер 1 + a).
Белле Прокофьевне каждый день необходимо принимать одну таблетку от жадности. Ко всеоб-
щему огорчению, и её болезнь сильнее лекарства, поэтому каждый день она глотает b таблеток.
Внешне эти таблетки выглядят совершенно одинаково и каждая из сестёр считает, что вот этот
пузырёк с n пилюлями именно её. На сколько дней им хватит этого количества лекарств?
Формат входных данных
Три строки входных данных содержат три целых числа a, b (1 a, b
100) и n (1 n
1018).
Обратите внимание, что значения переменных в этой задаче могут превышать воз-
можные значения 32-битной целочисленной переменной, поэтому необходимо исполь-
зовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long
в C++, тип long в Java и C#).
Формат выходных данных
Программа должна вывести одно число - ответ на задачу.
Система оценки
Решения, верно работающие при a = 1 (Аполлинария принимает лекарство каждый день), будут
оцениваться в 20 баллов.
Решения, верно работающие при n
105, будут оцениваться 40 баллов.
Примеры
стандартный ввод
стандартный вывод
2
3
3
12
3
0
4
2
Замечание
В первом примере Аполлинария Прокофьевна принимает по одной таблетке раз в два дня (на-
чиная с первого), Белла Прокофьевна принимает по три таблетки каждый день. В пузырьке 12
таблеток.
В первый день Аполлинария принимает одну таблетку, а Белла - три. В пузырьке осталось
восемь пилюль.
Во второй день Аполлинария забывает принять таблетку, а Белла опять съедает три. В пузырьке
осталось пять пилюль.
В третий день Аполлинария принимает одну таблетку, а Белла - три. В пузырьке осталась
последняя пилюля, ещё на один день этого количества сёстрам не хватит.
Во втором примере начального количества таблеток не хватит даже на один день.
Страница 2 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 3. Мастерство фотографии
Имя входного файла:
стандартный ввод
Имя выходного файла:
стандартный вывод
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Фотографа попросили сделать фотосессию группы детей для выпускного альбома в детском
саду. В числе прочих, он должен сделать групповой снимок, на котором должны присутствовать
все дети одновременно. Фотограф считает, что для красивой фотографии группы требуется очень
тщательно расставить детей в кадре. В частности, с его точки зрения, группа должна расположиться
как можно компактнее по ширине, то есть количество людей в самом длинном ряду на фотографии
должно быть как можно меньше.
Для гармоничного расположения детей фотограф размещает детей не более чем в четыре ряда.
Девочек он располагает либо во втором ряду, сидящими на стульчиках, либо стоящими в третьем
ряду. Мальчиков он размещает либо в первом ряду, сидящими на корточках, либо в четвёртом
ряду, стоящими на стульчиках. Группа состоит из a мальчиков и b девочек. В студии есть стулья в
количестве c штук. Какие-то ряды могут быть пустыми. Все стулья использовать не обязательно.
По заданным числам a, b и c требуется определить, какого наименьшего по ширине расположения
группы сможет добиться фотограф.
Формат входных данных
Программа получает на вход три целых неотрицательных числа a, b и c, записанных в отдельных
строках - количество мальчиков, девочек и стульев соответственно. Все числа не превосходят 1018.
Обратите внимание, что значения переменных в этой задаче могут превышать воз-
можные значения 32-битной целочисленной переменной, поэтому необходимо исполь-
зовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long
в C++, тип long в Java и C#).
Формат выходных данных
Вывести одно целое число - минимальную ширину группы, которую сможет организовать фо-
тограф.
Система оценки
Решения, правильно работающие при 0 a,b,c
50, будут оцениваться в 20 баллов.
Решения, правильно работающие при 0 a,b,c
1000, будут оцениваться в 30 баллов.
Решения, правильно работающие при 0 a,b,c
106, будут оцениваться в 50 баллов.
Кроме того, независимо от размера входных данных, решения, правильно работающие для слу-
чаев, когда все числа во входных данных чётные, будут оцениваться в 30 баллов.
Примеры
стандартный ввод
стандартный вывод
9
15
15
0
9
11
15
4
9
9
15
7
9
8
15
100
Страница 3 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Замечание
Во всех примерах в условии группа состоит из 9 мальчиков и 15 девочек.
В первом примере стульев нет, поэтому все девочки стоят, все мальчики сидят на корточках,
общая ширина группы 15.
Во втором примере есть 4 стула. Можно посадить 4 девочек во втором ряду на эти стулья,
остальные 11 девочек будут стоять в третьем ряду. Все мальчики будут сидеть на корточках в первом
ряду. Общая ширина группы 11.
В третьем примере есть 7 стульев. Тогда есть два способа получить группу ширины 9. Например,
можно посадить на все стулья девочек, тогда в первом ряду будет 9 мальчиков, во втором ряду будет
7 девочек, в третьем ряду 8 девочек. Либо можно посадить на стулья 6 девочек и поставить одного
мальчика в четвёртый ряд. Тогда получим 8 мальчиков в первом ряду, 6 девочек во втором, 9 девочек
в третьем и 1 мальчика в четвёртом. В любом из этих двух случаев ширина группы равна 9.
В четвёртом примере стульев много и есть несколько способов организовать группу ширины 8.
Один из способов такой: посадим на корточки 4 мальчика в первом ряду, далее посадим 8 девочек
на стулья во втором ряду, оставшиеся 7 девочек встанут в третьем и 5 мальчиков поставим на
стульчики в четвёртом.
Страница 4 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 4. Места в ряду
Имя входного файла:
стандартный ввод
Имя выходного файла:
стандартный вывод
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
В зале есть ряд из n мест, пронумерованных числами от 1 до n слева направо. Пройти к любому
месту можно либо с левого конца ряда, либо с правого. Первоначально некоторые места уже заняты
и ещё k человек по одному садятся на свободные места. Каждый человек выбирает себе свободное
место, до которого ближе всего идти от одного из концов ряда. Если же есть два свободных места,
одинаково удалённых от левого и правого концов ряда, то человек выберет левое место (с меньшим
номером).
Определите номера мест, которые будут выбирать люди, в порядке их прихода.
Формат входных данных
Первая строка входных данных содержит целое число n (1 n
2 · 105) - количество мест в
ряду.
Вторая строка содержит целое число k (1 k n) - количество приходящих людей.
Третья строка содержит строку s длины n, состоящую из символов «0» и «1» и задающую пер-
воначальную рассадку. Занятые места обозначаются единицами, пустые - нулями. Гарантируется,
что в строке s содержится не менее k нулей.
Формат выходных данных
Программа должна вывести k чисел - номера выбранных мест в порядке прихода новых людей.
Система оценки
Решения, правильно работающие при k = 1, будут оцениваться в 20 баллов.
Решения, правильно работающие, когда строка s состоит только из символов «0», будут оцени-
ваться в 32 балла.
Решения, правильно работающие при 1 k n
1000, будут оцениваться в 28 баллов.
Примеры
стандартный ввод
стандартный вывод
6
5 3
2
110001
6
1 6 3
3
010010
Замечание
В первом примере первоначально заняты места 1, 2 и 6 (рисунок А).
Если первый пришедший будет двигаться с левой стороны ряда, он пройдёт мимо 1 и 2 места,
прежде чем доберётся до свободного места с номером 3. Если же он будет двигаться с правой стороны
ряда, то ему понадобится пройти мимо одного места с номером 6, после чего он сможет занять место
5. Именно это место он и выберет (рисунок Б).
Второй пришедший может занять либо место с номером 3, двигаясь с левой стороны и проходя
мимо двух занятых мест 1 и 2, либо место с номером 4, двигаясь с правой стороны и проходя мимо
двух занятых мест 6 и 5. Поскольку в обоих случаях ему нужно пройти мимо двух занятых мест,
он будет двигаться с левой стороны и займёт место с номером 3.
Во втором примере в ряду 6 мест, второе и пятое места изначально уже заняты, заходят ещё 3
человека. Первый заходящий человек будет выбирать между первым и шестым местами, заходя с
левого или правого края соответственно. В обоих случаях ему придётся пройти мимо нуля занятых
мест, поэтому он решит зайти слева и сесть на 1 место. Второй человек будет выбирать между
Страница 5 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
третьим и шестым местами. В первом случае ему придётся идти мимо двух занятых мест, во втором
- мимо нуля, поэтому он выберет зайти справа - 6 место. Третий человек будет выбирать между
третьим и четвертым местами. В обоих случаях ему придётся пройти мимо двух занятых мест,
поэтому он выберет зайти слева - 3 место.
Страница 6 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Задача 5. Гармония
Имя входного файла:
стандартный ввод
Имя выходного файла:
стандартный вывод
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Совсем недавно Васе на день рождения подарили строку, состоящую только из символов «0»
и «1». Обрадованный этим подарком, он тут же начал эту строку изучать - искать в ней гармо-
ничные части. Для начала Васю интересует только количество различных непустых гармоничных
подстрок. А поскольку подарок оказался слишком большим, мальчик решил обратиться за помощью
к вам. Помогите Васе!
В понимании Васи, строка является гармоничной, если и символов 0, и символов 1 в ней чётное
количество.
Подстрокой строки s называется строка, полученная из s выкидыванием нескольких символов с
начала и с конца (возможно, нуля или всех). Так, строка «12» является подстрокой строки «123», а
строка «13» - нет. Подстроки считаются одинаковыми, если у них совпадает количество удалённых
символов с начала и с конца.
Формат входных данных
В первой строке дано одно число n - длина подарка (1 n
2 · 105).
Во второй строке дана строка s длины n - Васин подарок. Гарантируется, что s состоит только
из нулей и единиц.
Формат выходных данных
Выведите единственное число - количество различных гармоничных подстрок в s.
Обратите внимание, что значение ответа в этой задаче может превышать возможное
значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-
битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++,
тип long в Java и C#).
Система оценки
Решения, правильно работающие для строк, целиком состоящих из нулей, будут оцениваться
в 20 баллов.
Решения, правильно работающие при n
100, будут оцениваться в 20 баллов.
Решения, правильно работающие при n
1000, будут оцениваться в 30 баллов.
Примеры
стандартный ввод
стандартный вывод
6
7
001100
1
0
0
Замечание
В первом примере из условия подходят следующие подстроки (выделены жирным): 001100,
001100, 001100, 001100, 001100, 001100, 001100.
Страница 7 из 7
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Разбор задач
Максимальное количество баллов - 500
Задача 1. Змейка
При переходе от n к n + 1 добавляется одна линия длины 1 и две линии длины n + 1. Чтобы
набрать 40 баллов, можно написать цикл, суммирующий эти значения.
n = int ( input ( ) )
ans = 0
for i in range ( 1 , n + 1 ) :
ans += 2 ∗ i + 1
print ( ans )
Чтобы набрать 100 баллов необходимо заменить цикл на сумму арифметической прогрессии.
Раскрасим линии так, как показано на рисунке. Тогда длина красных линий равна n × (n + 1) (как
две суммы членов арифметической прогрессии от 1 до n), а длина чёрных линий равна n. Всего
получится n × (n + 2).
n = int ( input ( ) )
ans = n ∗ ( n + 2 )
print ( ans )
Задача 2. Две сестры
В первой подзадаче a = 1: каждый день сёстры принимают по b + 1 таблетке. Их хватит на
n
l (b+1) J дней (целая часть частного).
Во второй подзадаче (40 баллов) достаточно написать решение, моделирующее процесс по дням.
Заведём счетчик дней и будем определять, хватит ли нам оставшихся таблеток ещё на один день.
Цикл продолжается, пока у нас есть таблетки (n > 0). Внутри цикла уменьшаем значение n на b, а
также если номер шага цикла делится на a, то уменьшаем ещё раз на 1.
Цикл остановится, когда таблетки закончатся, то есть n :( 0. При этом, если оказалось, что
n < 0, то есть количество таблеток стало отрицательным, то таблеток не хватило при последней
итерации цикла, поэтому количество дней нужно уменьшить на 1. Пример такого решения:
a = int ( input ( ) )
b = int ( input ( ) )
n = int ( input ( ) )
day = 0
while n > 0 :
n -= b
i f day % a == 0 :
n -= 1
day += 1
i f n
< 0 :
Страница 1 из 8
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
day -= 1
print(day)
При большом n эта программа работает долго. Для полного решения заметим, что процесс имеет
период из a дней, за которые сёстры выпивают ab + 1 таблеток. Посчитаем количество полностью
завершённых циклов c, поделив n на ab + 1.
c = n // ( a ∗ b + 1 )
За эти дни будет принято c(ab + 1) таблеток. Вычтем это значение из n, получим количество
оставшихся таблеток. Их не хватит на полный цикл.
В первый день нового цикла сёстры выпьют b + 1 таблетку. Проверим, что n b + 1. Если да,
то добавим ещё один день, а также добавим количество последующих дней, в каждый из которых
только Белла Прокофьевна выпивает по b таблеток. Количество таких дней найдём целочисленным
делением на b.
Пример решения на языке Python.
a = int ( input ( ) )
b = int ( input ( ) )
n = int ( input ( ) )
pills_ in_ a_ days = a ∗ b + 1
c = n // pills_ in_ a_ days
days = c ∗ a
n %= pills_ in_ a_ days
i f n >= b + 1 :
days += 1
n -= b + 1
days += n // b
print ( days )
Ещё один быстрый способ решения этой задачи - двоичный поиск по ответу. Его можно приме-
нить, поскольку количество принимаемых таблеток с каждым днём увеличивается, а само количе-
ство выпитых таблеток за интересующее количество дней найти несложно.
a = int ( input ( ) )
b = int ( input ( ) )
n = int ( input ( ) )
l e f t = 0
r i g h t = n + 1
while r i g h t - l e f t
>
1 :
middle = ( l e f t
+
r i g h t ) // 2
p i l l s = middle
∗ b + 1 + ( middle - 1 )
// a
i f p i l l s > n :
r i g h t = middle
else :
l e f t = middle
print ( l e f t )
Задача 3. Мастерство фотографии
Рассмотрим разные по эффективности решения задачи.
Первое решение набирает 20 баллов. Переберём четырьмя вложенными циклами все возможные
варианты размеров рядов. Первый и четвёртый ряд могут содержать от 0 до a мальчиков, второй и
третий - от 0 до b девочек. Проверим, что сумма первого и четвёртого равна a, второго и третьего
равна b и сумма второго и четвёртого не превосходит c (последнее условие означает, что для такого
размещения хватит стульчиков).
Страница 2 из 8
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Такой подход позволяет решить задачу при a, b, c :( 50.
Пример решения на языке Python.
a = int ( input ( ) )
b = int ( input ( ) )
c = int ( input ( ) )
ans = 10∗∗18
for i 1 in range ( a + 1 ) :
for i 4 in range ( a + 1 ) :
for i 2 in range ( b + 1 ) :
for i 3 in range ( b + 1 ) :
i f i 1 + i 4 == a and i 2 + i 3 == b and i 2 + i 4 <= c :
ans = min( ans , max( i 1 , i 2 , i 3 , i 4 ) )
print ( ans )
Ускорим это решение. Заметим, что если мы определили число сидящих девочек (это значение i2
в примере выше), то число стоящих девочек перебирать не нужно, оно равно b - i2. Также нужно
перебирать только число стоящих на стульчиках мальчиков, получив число сидящих мальчиков
вычитанием. То есть мы будем перебирать только два значения: количество стульчиков, которые
заняли девочки, и количество стульчиков, занятых мальчиками. Нужно ещё проверить, что сумма
этих величин не превосходит c.
Такое решение проходит тесты, в которых a, b, c :( 1000 и набирает 30 баллов.
Пример решения на языке Python.
a = int ( input ( ) )
b = int ( input ( ) )
c = int ( input ( ) )
ans = 10∗∗18
for i in range ( a + 1 ) :
for j in range ( b + 1 ) :
i f i + j <= c :
ans = min( ans , max( i , a - i , j , b - j ) )
print ( ans )
Теперь рассмотрим два решения, содержащих один цикл.
Будем перебирать величину ans - значение самого широкого ряда, то есть мы хотим разместить
детей так, чтобы в каждом ряду было не более ans человек. Тогда мы можем посадить ans маль-
чиков на корточки в первом ряду, а оставшимся мальчикам понадобятся стульчики. Аналогично,
мы можем поставить ans девочек в третьем ряду, а оставшимся девочкам понадобятся стульчики.
Посчитаем количество нужных стульчиков, и если оно не превосходит c, то мы нашли подходя-
щий ответ (необходимо вывести минимальное значение ans, при котором хватило стульчиков для
размещения, также должно выполняться условие, что значения a и b не превышают 2 ∗ ans).
Такое решение пройдёт тесты в которых a, b, c :( 106, и наберёт от 50 до 70 баллов в зависимости
от используемого языка программирования. Пример такого решения:
a = int ( input ( ) )
b = int ( input ( ) )
c = int ( input ( ) )
ans = 1
while True :
na = max( 0 ,
a - ans )
# Кол-во стулье в для мальчиков
nb = max( 0 ,
b - ans )
# Кол-во стулье в для де воче к
i f a <= 2 ∗ ans and b <= 2 ∗ ans and na + nb <= c :
print ( ans )
break
ans += 1
Страница 3 из 8
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Во втором линейном решении переберём число стульев i, используемых для мальчиков от 0 до c.
Тогда девочкам останется c -i стульев.
Посчитаем ширину ряда, необходимую для размещения a мальчиков в двух рядах, если можно
использовать i стульев. Хотя бы в одном ряду окажется не менее, чем Ia/21 мальчиков (частное от
деления a/2, округлённое вверх, что можно вычислить по формуле (a + 1) // 2). Но также не менее
чем a - i мальчиков будут сидеть на корточках в первом ряду, т.к. число стульев для мальчиков
из четвёртого ряда не превышает i. Поэтому ширина наибольшего из двух рядов мальчиков есть
максимум из величин Ia/21 и a - i.
Посчитаем ширину максимального ряда у девочек, это максимум из Ib/21 и b - (c - i).
Это решение также пройдёт все тесты, где числа не превосходят 106, и наберёт от 50 до 72 баллов.
Пример решения на языке Python.
a = int ( input ( ) )
b = int ( input ( ) )
c = int ( input ( ) )
ans = 10∗∗18
for i in range ( c + 1 ) :
ma = max( ( a + 1 )
//
2 , a - i )
mb = max( ( b + 1 ) //
2 , b - ( c - i ) )
ans = min( ans , max(ma, mb) )
print ( ans )
Наконец, рассмотрим решения, набирающие 100 баллов.
Для начала рассмотрим решение при помощи двоичного поиска по ответу. Возьмём первое ре-
шение с одним циклом, в котором перебиралось значение ответа ans и заметим, что для небольших
значений ans невозможно расставить детей так, что ширина каждого ряда не превосходит ans, а
начиная с какого-то момента это становится возможно. Мы искали это минимальное подходящее
значение ans линейным поиском, но можно заменить его на двоичный поиск. Возьмём в качестве
значения left = 0 такое значение ans, которая заведомо не может быть ответом, а в качестве значе-
ния right = max(a, b) - значение ширины ряда, при котором рассадка заведомо возможна. Далее
будем сдвигать границы left и right, выбирая середину отрезка от left до right. Проверка того,
можно ли рассадить детей при выбранной допустимой ширине ряда, аналогична представленной в
решении с одним циклом.
Пример решения на языке Python.
a = int ( input ( ) )
b = int ( input ( ) )
c = int ( input ( ) )
l e f t = 0
r i g h t = max( a , b )
while r i g h t - l e f t > 1 :
m = ( l e f t + r i g h t )
// 2
c h a i r s = max( 0 , a - m) + max( 0 , b - m)
i f c h a i r s <= c and a <= 2 ∗ m and b <= 2 ∗ m:
r i g h t = m
else :
l e f t = m
print ( r i g h t )
Наконец обсудим полное решение, которое не содержит ни одного цикла и имеет сложность O(1).
Задачу можно решить при помощи нескольких условий и формул. Не ограничивая общности, будем
считать, что мальчиков не больше, чем девочек (a :( b), иначе поменяем a и b местами, т.к. условие
в некотором смысле «симметрично» для мальчиков и девочек.
Страница 4 из 8
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
Рассмотрим сначала случай, когда стульев нет совсем. Тогда ответом является число b - все
девочки стоят. Если теперь начать добавлять стулья, то количество стоящих девочек станет умень-
шаться на 1 c каждым дополнительным стулом, до тех пор, пока оно не сравняется с количеством
мальчиков. То есть если количество стульев c не превосходит разности b - a, то каждый дополни-
тельный стул будет уменьшать ответ на 1, то есть при c :( b - a ответом будет b - c.
Пусть c > b - a. Тогда мы уже использовали b - a стульев, чтобы уравнять количество девочек
без стульев (стоящих) с количеством мальчиков. Вычтем из значения c значение b - a, получим ко-
личество оставшихся стульев. Сейчас есть b-a сидящих девочек во втором ряду, a стоящих девочек
в третьем ряду и a сидящих на корточках мальчиков в первом ряду. Самые широкие ряды - это
первый и третий. Чтобы уменьшить их ширину на 1, теперь нужно 2 стула (один стул для маль-
чика, другой - для девочки). Поэтому поделив c на 2 (нацело), мы получим количество мальчиков
и девочек, на которое может быть уменьшена ширина первого и третьего рядов, то есть ответом
будет a - lc/2J.
Но также нужно учесть, что и в первом, и во втором случае ответ не может быть меньше значения
половины от числа девочек, округлённого вверх, то есть при вычислении ответа в каждом случае
нужно ещё взять максимум найденного значения и значения (b + 1) // 2.
Пример решения на языке Python.
a = int ( input ( ) )
b = int ( input ( ) )
c = int ( input ( ) )
i f a > b :
a , b = b , a
i f b - c >= a :
print (max( b - c ,
( b + 1 )
//
2 ) )
else :
c -= b - a
print (max( a - c
//
2 ,
( b + 1 )
//
2 ) )
Задача 4. Места в ряду
В первой подзадаче k = 1, то есть нам нужно обработать только одного нового человека. Мож-
но написать цикл, который просто переберёт все места, для каждого свободного места посчитает
расстояние до краёв и выберет место с минимальным расстоянием.
n = int ( input ( ) )
k = int ( input ( ) )
s = input ( )
ans = 0
min_dist = n + 1
for i in range ( n ) :
i f s [ i ] ==
’ 0 ’ :
d i s t = min( i + 1 , n - i )
i f d i s t < min_dist :
min_dist = d i s t
ans = i
print ( ans + 1 )
Во второй подзадаче строка s состоит только из символов «0». Можно заметить, что, так как все
места изначально свободны, места будут браться поочерёдно с левого и правого краёв, т.е. в после-
довательности 1, n, 2, n-1, 3, n-2,... Нужно вывести k первых элементов этой последовательности.
n = int ( input ( ) )
k = int ( input ( ) )
Страница 5 из 8
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
s = input ( )
for i in range ( k ) :
i f i % 2 == 0 :
print ( 1 + i
//
2 )
else :
print ( n - i
//
2 )
В третьей подзадаче n :( 1000, можно написать решение для общего случая, но неэффективное.
Можно взять первое решение и k раз находить ответ, затем изменять в строке символ «0» на «1»,
тем самым делая найденное место занятым.
n = int ( input ( ) )
k = int ( input ( ) )
s = input ( )
for j in range ( k ) :
ans = 0
min_dist = n + 1
for i in range ( n ) :
i f s [ i ] ==
’ 0 ’ :
d i s t = min( i + 1 , n - i )
i f d i s t < min_dist :
min_dist = d i s t
ans = i
print ( ans + 1 )
s = s [ : ans ] + " 1 " + s [ ans + 1 : ]
Заметим, что если какой-то вновь пришедший человек занял место «слева», то следующий че-
ловек может взять только место с большим номером, причём это окажется следующее свободное
место слева. Аналогично, если кто-то занял какое-то место справа, то следующее занятое справа
место будет иметь меньший номер. Поэтому не надо каждый раз просматривать все имеющиеся ме-
ста, а достаточно только найти первое свободное место слева и ближайшее свободное место справа,
выбрать наибольшее подходящее из них, а для следующего человека продолжать поиск с тех мест,
которые были найдены ранее.
Пусть i и j указывают на два равноудалённых от краёв места, i - от левого края, а j - от правого
края. Начнём со значений i=1 и j=n. Если из этих двух место одно - свободно, то нужно занять его,
а если оба свободны - то нужно занять левое. При обработке нового пришедшего человека будем
увеличивать i и уменьшать j, пока среди этих мест не найдётся свободное. Если окажется свободным
место i, то выберем его, иначе выберем место j. При выборе места заменим соответствующий символ
«0» в строке на «1», чтобы не выбрать это место повторно.
Пример решения на языке Python.
n = int ( input ( ) )
k = int ( input ( ) )
s = [ " 1 " ] + l i s t ( input ( ) )
i = 1
j = n
for _ in range ( k ) :
while s [ i ] ==
’ 1 ’ and s [ j ] ==
’ 1 ’ :
i += 1
j -= 1
i f s [ i ] ==
" 0 " :
print ( i )
s [ i ] = " 1 "
else :
print ( j )
Страница 6 из 8
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
s [ j ] = " 1 "
В этой реализации мы добавляем в начало строки ещё один фиктивный элемент «1», чтобы эле-
менты строки нумеровались от 1 до n. Также поскольку в Python строки - неизменяемые объекты,
то для быстрой замены элемента строки мы преобразуем строку в список из символов «0» и «1»,
тогда можно будет выполнять присваивания вида s[ i ] = "1".
Задача 5. Гармония
В первой подзадаче строка состоит только их одних нулей, поэтому любая подстрока чётной
длины является гармонической. Нужно подсчитать количество подстрок чётной длины в строке
длины n. Заметим, что подстрок длины k в строке будет n - k + 1, поэтому можно просуммировать
в цикле значения n-k + 1 для k = 2, 4, 6,
Можно вместо цикла использовать формулу для суммы
арифметической прогрессии, но это не требуется в данной подзадаче.
n = int ( input ( ) )
s = input ( )
ans = 0
for k in range ( 2 , n + 1 ,
2 ) :
ans += n - k + 1
print ( ans )
Дальнейшие подзадачи предполагают общее решение, но разной алгоритмической сложности.
Решение сложности O(n3) можно получить, если перебрать начало подстроки i и конец под-
строки j и для рассматриваемой подстроки проверить выполнение условия подсчётом числа нулей
и единиц.
n = int ( input ( ) )
s = input ( )
ans = 0
for i in range ( n ) :
for j in range ( i + 1 , n + 1 ) :
c0 = 0
c1 = 0
for t in range ( i , j ) :
i f s [ t ] ==
’ 0 ’ :
c0 += 1
else :
c1 += 1
i f c0 % 2 == 0 and c1 % 2 == 0 :
ans += 1
print ( ans )
Сложность этого решения можно улучшить, если избавиться от вложенного цикла по t. Для
этого заметим, что, когда правая граница j увеличивается на 1, не нужно пересчитывать значения
c0 и c1 заново, достаточно только учесть один новый добавленный символ. Такое решение будет
иметь сложность O(n2).
n = int ( input ( ) )
s = input ( )
ans = 0
for i in range ( n ) :
c0 = 0
c1 = 0
for j in range ( i , n ) :
i f s [ j ] ==
’ 0 ’ :
c0 += 1
Страница 7 из 8
Пригласительный этап всероcсийской олимпиады по информатике для 8-10 классов
Образовательный центр «Сириус», 23-24 мая 2024
else :
c1 += 1
i f c0 % 2 == 0 and c1 % 2 == 0 :
ans += 1
print ( ans )
Полное решение имеет сложность O(n). Будем рассматривать все префиксы исходной строки,
то есть первые j символов, увеличивая значение j. Для данного префикса длины j посчитаем ко-
личество нулей и единиц на этом префиксе в переменных c0 и c1. Эти значения на самом деле не
требуется пересчитывать заново, а нужно только учесть один новый добавляемый символ. Теперь
мы хотим определить, сколько подстрок исходной строки, у которых правая граница совпадает с j,
являются гармоничными. Такие строки получаются из рассматриваемого префикса отбрасыванием
какого-то другого, меньшего префикса (в том числе, возможно, и пустого префикса). При этом что-
бы получилась гармоничная подстрока, мы должны отбросить такой префикс, на котором чётность
числа нулей совпадает с чётностью c0, а чётность числа единиц совпадает с чётностью c1. Значит,
нам нужно знать, сколько ранее мы рассмотрели префиксов, у которых число нулей и число единиц
имеет определённую чётность.
Давайте для каждого префикса определим его тип. Типом назовём пару из остатка от деления
количества нулей на префиксе на 2 и остатка от деления количества единиц на префиксе на 2. Таким
образом, рассмотрев какой-то префикс, нужно добавить к ответу число, равное количеству ранее
рассмотренных префиксов такого же типа.
Пример такого решения на языке Python.
n = int ( input ( ) )
s = input ( )
count = [ [ 0 ,
0 ] ,
[ 0 ,
0 ] ]
ans = 0
c0 = 0
c1 = 0
count [ 0 ] [ 0 ] = 1
for c in s :
i f c ==
’ 0 ’ :
c0 += 1
else :
c1 += 1
ans += count [ c0 % 2 ] [ c1 % 2 ]
count [ c0 % 2 ] [ c1 % 2 ] += 1
print ( ans )
В этом решении в массиве count хранится количество префиксов каждого из четырёх типов.
Например, count [0][0] равен количеству префиксов, у которых чётное число нулей и чётное число
единиц. count [1][0] равен количеству префиксов, у которых нечётное число нулей и чётное число
единиц. count [0][1] равен количеству префиксов, у которых чётное число нулей и нечётное число
единиц. count [1][1] равен количеству префиксов, у которых нечётное число нулей и нечётное число
единиц.
В самом начале count [0][0] равен 1, что соответствует пустому префиксу (у него чётное число
нулей и единиц), остальные значения count равны 0.
Рассматриваем следующий символ, в зависимости от его значения изменяем c0 или c1. Тип
получившегося префикса есть [c0 % 2][c1 % 2]. Добавим к ответу count[c0 % 2][c1 % 2] и увеличим
это значение на 1, чтобы учесть этот префикс в дальнейшем.
Страница 8 из 8
Школьный этап всероcсийской олимпиады по информатике для 5-6 классов
22 октября 2024
Задача 1. Квадрат
В квадрате 3 × 3 расставили числа от 1 до 9. Затем внутри этого квадрата взяли все квадраты
2 × 2 и посчитали сумму чисел в каждом их них, а потом сложили все полученные суммы.
Расставьте числа от 1 до 9 в квадрате так, чтобы полученная сумма была как можно больше.
Каждое из чисел от 1 до 9 должно встречаться в вашем ответе ровно один раз.
В ответе запишите 3 строки, в каждой строке должно быть 3 числа через пробел.
Задача 2. Переправа
Семье из мамы и пяти детей в возрасте 5, 6, 7, 8 и 9 лет нужно переправиться через реку, с левого
берега на правый. У них есть лодка, которая может вместить маму (которая обязательно должна
плыть в лодке) и не более, чем двух детей.
Если на берегу без мамы останутся два ребёнка, возраст которых отличается на 1 год (то есть
5 и 6 лет или 6 и 7 лет и т.д.), то они подерутся. Составьте план переправы через реку так, чтобы
никто не подрался.
Запишите несколько строк, каждая из которых содержит одно или два числа, соответствующие
возрасту детей (то есть одно или два числа из множества 5, 6, 7, 8, 9). Мама переплывает реку на
каждом шаге. Если мама переплывает реку без детей, напишите в этой строке знак «-».
Нечётные строки соответствуют перемещению лодки с левого берега на правый, чётные строки -
в противоположном направлении.
Чем меньше строк будет в вашем ответе, тем больше баллов вы получите.
Задача 3. Чаепитие
Слон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный
стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб.
Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем
всё варенье, и затем весь чай.
Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять
местамитолько два соседних предмета. Обозначим хлеб буквой«Х», варенье буквой «В», чай буквой
«Ч». Тогда последовательность предметов на столе задаётся строкой из этих букв. Например, при
расстановке предметов «ВЧXВ» на подготовку стола потребуются три секунды. Предметы, которые
переставляются местами каждую секунду, подчёркнуты.
1. ВХЧВ
2. ХВЧВ
3. ХВВЧ
Слон торопится, и поэтому хочет знать, при какой первоначальной расстановке предметов у него
уйдёт наибольшее время на подготовку стола.
Вам нужно дать ответ для четырёх случаев: когда на столе у Семёна стоит 3, 6, 7 и 8 предметов.
Для каждого из этих случаев вы должны записать в ответе строку, состоящую из необходимого
количества букв, каждая буква должна быть одной из букв «Х», «В», «Ч». Количество предметов
каждого вида вы можете выбрать самостоятельно, но общее число букв в ответе должно быть равно
3, 6, 7 и 8. Вы должны найти такую расстановку предметов, при которой подготовка стола займёт
наибольшее время для данного числа предметов.
В ответе напишите четыре строки, в первой строке ответ для 3 предметов, во второй строке -
для 6 предметов, в третьей строке - для 7 предметов, в четвёртой строке - для 8 предметов. Вы
должны записать в ответе 4 строки, если вы не можете найти ответ для какого-то случая, напишите
любую строку из букв «Х», «В», «Ч» нужной длины.
Страница 1 из 2
Школьный этап всероcсийской олимпиады по информатике для 5-6 классов
22 октября 2024
Задача 4. Набор на кружки
Учащиеся школы должны выбрать себе дополнительные занятия на год. Каждый из них выбрал
как минимум один предмет из предложенных: биологии, музыки и шахмат. Известно, что 150
школьников выбрали биологию, 130 учеников - музыку и 100 - шахматы, но каждый учащийся
мог выбрать и несколько предметов.
Ответьте на вопросы:
1. Какое минимальное количество учащихся могло быть в школе?
2. Какое максимальное количество учащихся могло быть в школе?
3. Считайте, что одновременно биологию и музыку выбрали 85 учащихся. Сколько школьников
выбрало ровно один из этих двух предметов?
4. Считайте, что ни один школьник не выбрал одновременно биологию и шахматы, одновременно
биологию и музыку выбрали 60 человек, а всего в школе 250 учащихся. Сколько школьников
выбрало и шахматы, и музыку?
5. Считайте, что в ситуации из пункта 4 на кружки разрешили записываться учащимся дру-
гих школ. Какое минимальное дополнительное количество школьников должно записаться на
предложенные предметы, чтобы количество людей, посещающих только музыку, стало рав-
няться количеству людей, не посещающих её?
В ответе запишите пять целых чисел, каждое число - в отдельной строке. Если вы не можете
дать ответ на какой-то вопрос, запишите в ответе любое число.
Задача 5. Кратчайший поезд
Вам необходимо составить поезд из нескольких последовательно сцепленных вагонов, обозна-
ченных буквами.
1. Грузовой вагон (F). Таких вагонов в поезде должно быть 5.
2. Вагон с ценностями (V). Таких вагонов в поезде должно быть 5.
3. Вагон с охраной (G).
4. Локомотив (L).
При этом требуется соблюсти следующие правила.
1. Первым и последним вагонами поезда должны быть локомотивы (L).
2. Посередине поезда также должны располагаться дополнительные вагоны-локомотивы. В по-
езде не должно быть цепочки из подряд идущих 8 и более вагонов без локомотива.
3. Каждый вагон с ценностями (V) должен быть непосредственно прицеплен к вагону с охраной
(G).
4. Каждый грузовой вагон (F) должен быть прицеплен к вагону с охраной (G) или другому
вагону, прицепленному к вагону с охраной (то есть между грузовым вагоном и вагоном с
охраной находится один вагон).
Составьте поезд, удовлетворяющий этим условиям и содержащий наименьшее число вагонов. В
вашем поезде должно быть ровно 5 грузовых вагонов (F) и ровно 5 вагонов с ценностями (V).
В ответ запишите последовательность букв, обозначающих вагоны. Чем короче будет ваш ответ,
тем больше баллов вы получите.
Страница 2 из 2
Школьный этап всероcсийской олимпиады по информатике для 5-6 классов
22 октября 2024
Разбор задач
Задача 1. Квадрат
Центральная клетка принадлежит четырём квадратам 2 × 2, четыре клетки посередине сторон -
двум квадратам каждая, а клетки в углах - только одному квадрату. Поэтому в центре должно
стоять число 9, а в углах - числа 1, 2, 3, 4. На серединах сторон должны стоять числа 5, 6, 7, 8.
Любой ответ, соответствующий этим условиям, будет правильным.
1 5 2
6 9 7
3 8 4
Задача 2. Переправа
Сначала нужно перевезти детей 6 и 8 лет, это единственный способ оставить на левом берегу
троих (5, 7 и 9 лет) так, чтобы избежать конфликта. Затем мама должна вернуться назад и перевезти
любых двоих из оставшихся на левом берегу детей, но обратно ей придётся вернуться с детьми 6 и
8 лет. Их она оставит на левом берегу, перевезёт того оставшегося ребёнка, который ждёт на левом
берегу с самого начала, вернётся и заберёт детей 6 и 8 лет. Пример такого решения.
6 8
-
5 9
6 8
7
-
6 8
Задача 3. Чаепитие
Для чаепития необходима такая расстановка предметов: Х, ..., Х, В, ..., В, Ч, ...Ч. Нам необходимо
получить перестановку предметов, для которой получение такой последовательности потребовало
бы как можно больше операций. Поэтому в ответе не могут идти буквы Х и В подряд, иначе,
переставив их местами, мы получим большее число операций. Также подряд не могут идти буквы
В и Ч. То есть ответ всегда имеет вид Ч, ..., Ч, В, ..., В, Х, ..., Х. Осталось только понять, сколько
нужно взять чая, варенья и хлеба в ответе.
Пусть в ответе чай встречается x раз, варенье встречается y раз, хлеб встречается z раз,
x + y + z = n. Посчитаем количество секунд, необходимых для приведения такой перестановки
в порядок. Нам придётся поменять местами каждую порцию чая и варенья, это займёт xy секунд.
Аналогично понадобится yz секунд, чтобы поменять варенье и хлеб и xz секунд, чтобы поменять
чай и хлеб. Нужно подобрать такие значения x, y, z, чтобы сумма xy + yz + xz была максимальной.
Интуитивно понятно, что числа должны быть равны или близки (отличаться на 1). Докажем
это. Пусть, например, числа x и y отличаются на 2 и более, то есть x y + 2. Рассмотрим новую
последовательность, в которой x будет на 1 меньше, а y увеличим на 1. Тогда для новой последо-
вательности ответ равен (x - 1)(y + 1) + (x - 1)z + (y + 1)z = xy + x - y - 1 + xz + yz, то есть
ответ изменится на x - y - 1, и если x - y
2, то продолжительность увеличится. Таким образом,
в правильном ответе среди чисел x, y, z не должно быть различающихся на 2 и более.
Итак, если n делится на 3, то необходимо взять x = y = z = n/3. Если n не делится на 3, то одно
или два из этих чисел нужно увеличить на 1, в зависимости от остатка от деления n на 3.
Возможный правильный ответ:
ЧВХ ЧЧВВХ
Х ЧЧВВХХХ
ЧЧЧВВХХХ
Страница 1 из 2
Школьный этап всероcсийской олимпиады по информатике для 5-6 классов
22 октября 2024
Задача 4. Набор на кружки
1. Так как 150 школьников выбрали биологию, количество учеников в школе не может быть
меньше 150. Но оно может быть равно 150, если все ученики будут выбирать биологию и ещё
одно или два дополнительных занятия.
2. Наибольшее число учеников в школе окажется в случае, если все выбрали разные занятия.
Тогда число учеников будет равно 150 + 130 + 100 = 380.
3. Если и биологию, и музыку выбрали 85 учащихся, то только биологию выбрали 150 - 85 = 65
учащихся, только музыку выбрали 130 - 85 = 45, а ровно один из этих предметов выбрали
65 + 45 = 110 школьников.
4. Поскольку из 250 учащихся биологию выбрали 100 учащихся, шахматы 150, и никто не вы-
брал и шахматы, и биологию одновременно, то каждый учащийся обязательно выбрал или
биологию, или шахматы, то есть нет учащихся, выбравших только музыку. Каждый учащий-
ся, выбравший музыку, выбрал ещё один предмет. При этом музыку и биологию выбрали 60
учащихся, значит, музыку и шахматы выбрали 130 - 60 = 70 учащихся.
5. В предыдущем пункте музыку посещают 130 человек, а не посещают 250 - 130 = 120 чело-
век, при этом только музыку не посещает никто. Чтобы число учеников, посещающих только
музыку, стало равным числу учеников, не посещающих музыку, необходимо, чтобы 120 новых
школьников записались только на музыку.
Задача 5. Кратчайший поезд
Рассмотрим сцепку из вагонов FVGVF. Она удовлетворяет условиям размещения грузовых ваго-
нов и вагонов с ценностями рядом с вагонами охраны и содержит два грузовых вагона и два вагона
с ценностями. Нам необходимо использовать две такие сцепки, а ещё в одной сцепке оставить только
один вагон с ценностями и один грузовой вагон. Между сцепками вставим локомотивы, получим
такое решение:
LFVGVFLFVGVFLGVFL
В этом решении мы использовали минимальное число вагонов охраны, но количество локомоти-
вов можно сократить. Поставим в центр один локомотив, одну сцепку разместим в начале поезда,
ещё одну сцепку - в конце. Нам осталось разместить ещё один грузовой вагон и вагон с ценностями,
также нам понадобится один вагон охраны. Поскольку длина сцепки равна 5, а подряд могут идти
7 вагонов без локомотива, то слева и справа от центрального локомотива можно разместить ещё по
два вагона с каждой стороны. Разместим в центре конструкцию FLGV. Она удовлетворяет усло-
вию размещения грузовых вагонов и вагонов с ценностями, и в итоге мы обошлись только одним
дополнительным локомотивом. Возможный ответ:
LFVGVFFLGVFVGVFL
Страница 2 из 2
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
Задача 1. Набор на кружки
Учащиеся школы должны выбрать себе дополнительные занятия на год. Каждый из них выбрал
как минимум один предмет из предложенных: биологии, музыки и шахмат. Известно, что 150
школьников выбрали биологию, 130 учеников - музыку и 100 - шахматы, но каждый учащийся
мог выбрать и несколько предметов.
Ответьте на вопросы:
1. Какое минимальное количество учащихся могло быть в школе?
2. Какое максимальное количество учащихся могло быть в школе?
3. Считайте, что одновременно биологию и музыку выбрали 85 учащихся. Сколько школьников
выбрало ровно один из этих двух предметов?
4. Считайте, что ни один школьник не выбрал одновременно биологию и шахматы, одновременно
биологию и музыку выбрали 60 человек, а всего в школе 250 учащихся. Сколько школьников
выбрало и шахматы, и музыку?
5. Считайте, что в ситуации из пункта 4 на кружки разрешили записываться учащимся дру-
гих школ. Какое минимальное дополнительное количество школьников должно записаться на
предложенные предметы, чтобы количество людей, посещающих только музыку, стало рав-
няться количеству людей, не посещающих её?
В ответе запишите пять целых чисел, каждое число - в отдельной строке. Если вы не можете
дать ответ на какой-то вопрос, запишите в ответе любое число.
Задача 2. Чаепитие
Слон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный
стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб.
Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем
всё варенье, и затем весь чай.
Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять
местамитолько два соседних предмета. Обозначим хлеб буквой«Х», варенье буквой «В», чай буквой
«Ч». Тогда последовательность предметов на столе задаётся строкой из этих букв. Например, при
расстановке предметов «ВЧXВ» на подготовку стола потребуются три секунды. Предметы, которые
переставляются местами каждую секунду, подчёркнуты.
1. ВХЧВ
2. ХВЧВ
3. ХВВЧ
Слон торопится, и поэтому хочет знать, при какой первоначальной расстановке n предметов у
него уйдёт наибольшее время на подготовку стола.
Вам нужно дать ответ для четырёх значений n равных 3, 9, 11, 13. Для каждого из этих n
вы должны записать в ответе строку, состоящую из n букв, каждая буква должна быть одной из
букв «Х», «В», «Ч». Количество предметов каждого вида вы можете выбрать самостоятельно, но в
ответе должно быть ровно n букв. Вы должны найти такую расстановку предметов, при которой
подготовка стола займёт наибольшее время для данного числа предметов.
В ответе напишите четыре строки, в первой строке ответ для n = 3, во второй строке - для
n = 9, в третьей строке - для n = 11, в четвёртой строке - для n = 13. Вы должны записать
ответы для всех четырёх значений n, если вы не можете найти ответ для какого-то n, напишите
любую строку из n букв «Х», «В», «Ч».
Страница 1 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
Задача 3. Кратчайший путь
Есть 7 городов, обозначенных буквами английского алфавита A, B, C, D, E, F, G. Вы хотите
посетить эти все города ровно по одному разу каждый и вернуться в начальную точку своего путе-
шествия. Для этого вы можете воспользоваться самолётами: между двумя любыми городами есть
прямой авиарейс. Стоимость перелёта между парой городов приведена в следующей таблице.
A
B
C
D
E
F
G
A
-
5
2
4
1
6
3
B
5
-
4
6
3
8
7
C
2
4
-
5
8
3
1
D
4
6
5
-
2
7
8
E
1
3
8
2
-
4
6
F
6
8
3
7
4
-
5
G
3
7
1
8
6
5
-
Необходимо построить замкнутый маршрут, проходящий через все города по одному разу, стои-
мость перелёта по которому была бы минимально возможной.
В ответе укажите какую-то перестановку из 7 букв A, B, C, D, E, F, G в том порядке, в котором
вы будете посещать города. Каждая буква должна встречаться ровно по одному разу. Чем короче
будет найденный вами маршрут, тем больше баллов вы получите. Обратите внимание, при расчёте
стоимости маршрута также учитывается перелёт из последнего города вашего ответа в первый
город.
Задача 4. Путешествие
Данис живёт на клетчатой плоскости и может перемещаться по плоскости в одном из четырёх
направлений: направо, налево, вверх, вниз. За один шаг он перемещается на единицу длины. Ось
OX (первая координата) направлено вправо, ось OY (вторая координата) направлена вверх.
Данис начинает путь в точке (0; 0). Например, если он выполнит четыре команды перемещения
«направо», «вниз», «налево», «вверх», то посетит следующие точки: (1; 0), (1; -1), (0; -1), (0; 0).
Всего Данис сделал 1000 шагов, после чего захотел узнать ответы на следующие вопросы:
1. Сколько раз Данис прошёл через точку (-11, 9)?
2. Какое количество различных точек посетил Данис?
3. В какой точке Данис побывал больше всего раз? В ответе координаты разделяйте пробелом.
4. Какая посещённая им точка находится ближе всего к точке (10, 6)? Расстоянием между точ-
ками считается количество ходов, которые нужно сделать для того, чтобы попасть из одной
точки в другую, то есть так называемое «манхэттенское расстояние». В ответе координаты
разделяйте пробелом.
Для выполнения задания вы можете использовать электронные таблицы из офисного пакета или
любые другие средства вашего компьютера. Вы можете скачать файл с данными для выполнения
этого задания в одном из двух форматов: Microsoft Excel (XLSX) или LibreOffice Calc (ODS).
В этой таблице в единственном столбце с данными A содержится последовательность перемеще-
ний Даниса.
В ответе запишите четыре строки: ответы на четыре вопроса. В первой и второй строке должно
быть по одному целому числу, в третьей и четвёртой строке - по два целых числа, через пробел
(координаты точек). Если вы не знаете ответ на какой-нибудь вопрос, запишите вместо него любое
число или любую точку (два числа).
Страница 2 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
Задача 5. Качели
Ограничение по времени:
0.5 секунд
Трое друзей - Аня, Боря и Саш - пришли на детскую площадку, чтобы покачаться на качелях-
балансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети
садятся с разных концов.
Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух
концах качелей должна быть не более D кг. Друзьям повезло: рядом с площадкой оказалась груда
достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать
разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу
камня, благодаря которому они смогут покачаться на качелях.
Формат входных данных
Программа получает на вход три числа A, B, C, записанных в отдельных строках, - массы
друзей. В четвёртой строке записано число D - наибольшая допустимая разница масс на концах
качелей. Все числа - целые, положительные и не превосходящие 109.
Формат выходных данных
Программа должна вывести одно целое число - минимальную необходимую массу камня, ко-
торую нужно добавить на одну из сторон качелей, чтобы друзья смогли покачаться на них, сев
оптимально. Если камень им не понадобится, программа должна вывести число 0.
Система оценки
Решения, правильно работающие, когда все входные числа не превосходят 105, будут оцениваться
в 40 баллов.
Примеры
стандартный ввод
стандартный вывод
30
15
40
35
10
30
0
20
45
10
Замечание
В первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На
другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит
55 кг. Разница весов на концах качелей примет значение 10 кг.
Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша - на другую сторону (45 кг).
Разница весов будет равна 5 кг, поэтому камень не понадобится.
Страница 3 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
Задача 6. Фонари
Ограничение по времени:
1 секунда
Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние
между домами за единицу длины.
Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут
освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на
расстоянии Y (включительно). В частности, при X = 0 или Y = 0 такой фонарь освещает только
тот дом, у которого он установлен.
Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены.
Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами
необязательно.
Формат входных данных
Первая строка входных данных содержит целое число N (1 N
105). Следующие четыре
строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосхо-
дят 105.
Формат выходных данных
Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая
строка должна содержать два целых числа черезпробел - координату фонаря и расстояние,которое
он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1
до N, рядом с каждым домом можно поставить только один фонарь.
При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не
существует, программа должна вывести одно число -1.
Система оценки
Решения, правильно работающие при A = 0 или B = 0, будут оцениваться в 30 баллов.
Решения, правильно работающие при A /= 0, B /= 0, n
1000, будут оцениваться в 40
баллов.
Примеры
стандартный ввод
стандартный вывод
10
2 1
3
5 2
1
9 1
1
2
10
-1
1
1
1
2
Замечание
В ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 -
также дома 3, 4, 6 и 7, а фонарь у дома 9 - также дома 8 и 10. В результате все дома освещены.
Во втором примере фонарей недостаточно.
Страница 4 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
Задача 7. Деление шоколадки
Ограничение по времени:
1 секунда
У Маши есть прямоугольная шоколадка, состоящая из m × n квадратных долек. Маша хочет
разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков,
то есть каждому другу достанется прямоугольный кусочек шоколадки.
У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре
достался самый большой кусок (содержащий как можно больше долек). Определите число долек в
этом куске.
Формат входных данных
Программа получает на вход три натуральных числа, каждое в отдельной строке: m, n и k. Все
числа - целые положительные, при этом m и n не превосходят 106, а k mn.
Обратите внимание на то, что значение mn, а, значит, и значение k в этой задаче
может превышать возможное значение 32-битной целочисленной переменной, поэтому
необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке
Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Программа должна вывести одно целое число - максимально возможное количество долек в
том прямоугольном куске, который получит Юра.
Система оценки
Решения, правильно работающие при m
1000 и n
1000, будут оцениваться в 60 баллов.
Пример
стандартный ввод
стандартный вывод
4
16
5
4
Замечание
В примере из условия нужно разделить шоколадку 4 × 5 на 4 кусочка. Самый большой кусочек
будет состоять из 16 долек, как показано на картинке.
Страница 5 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
Разбор задач
Задача 1. Набор на кружки
1. Так как 150 школьников выбрали биологию, количество учеников в школе не может быть
меньше 150. Но оно может быть равно 150, если все ученики будут выбирать биологию и ещё
одно или два дополнительных занятия.
2. Наибольшее число учеников в школе окажется в случае, если все выбрали разные занятия.
Тогда число учеников будет равно 150 + 130 + 100 = 380.
3. Если и биологию, и музыку выбрали 85 учащихся, то только биологию выбрали 150 - 85 = 65
учащихся, только музыку выбрали 130 - 85 = 45, а ровно один из этих предметов выбрали
65 + 45 = 110 школьников.
4. Поскольку из 250 учащихся биологию выбрали 100 учащихся, шахматы 150, и никто не вы-
брал и шахматы, и биологию одновременно, то каждый учащийся обязательно выбрал или
биологию, или шахматы, то есть нет учащихся, выбравших только музыку. Каждый учащий-
ся, выбравший музыку, выбрал ещё один предмет. При этом музыку и биологию выбрали 60
учащихся, значит, музыку и шахматы выбрали 130 - 60 = 70 учащихся.
5. В предыдущем пункте музыку посещают 130 человек, а не посещают 250 - 130 = 120 чело-
век, при этом только музыку не посещает никто. Чтобы число учеников, посещающих только
музыку, стало равным числу учеников, не посещающих музыку, необходимо, чтобы 120 новых
школьников записались только на музыку.
Задача 2. Чаепитие
Для чаепития необходима такая расстановка предметов: Х, ..., Х, В, ..., В, Ч, ...Ч. Нам необходимо
получить перестановку предметов, для которой получение такой последовательности потребовало
бы как можно больше операций. Поэтому в ответе не могут идти буквы Х и В подряд, иначе,
переставив их местами, мы получим большее число операций. Также подряд не могут идти буквы
В и Ч. То есть ответ всегда имеет вид Ч, ..., Ч, В, ..., В, Х, ..., Х. Осталось только понять, сколько
нужно взять чая, варенья и хлеба в ответе.
Пусть в ответе чай встречается x раз, варенье встречается y раз, хлеб встречается z раз,
x + y + z = n. Посчитаем количество секунд, необходимых для приведения такой перестановки
в порядок. Нам придётся поменять местами каждую порцию чая и варенья, это займёт xy секунд.
Аналогично понадобится yz секунд, чтобы поменять варенье и хлеб и xz секунд, чтобы поменять
чай и хлеб. Нужно подобрать такие значения x, y, z, чтобы сумма xy + yz + xz была максимальной.
Интуитивно понятно, что числа должны быть равны или близки (отличаться на 1). Докажем
это. Пусть, например, числа x и y отличаются на 2 и более, то есть x y + 2. Рассмотрим новую
Страница 1 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
последовательность, в которой x будет на 1 меньше, а y увеличим на 1. Тогда для новой последо-
вательности ответ равен (x - 1)(y + 1) + (x - 1)z + (y + 1)z = xy + x - y - 1 + xz + yz, то есть
ответ изменится на x - y - 1, и если x - y
2, то продолжительность увеличится. Таким образом,
в правильном ответе среди чисел x, y, z не должно быть различающихся на 2 и более.
Итак, если n делится на 3, то необходимо взять x = y = z = n/3. Если n не делится на 3, то одно
или два из этих чисел нужно увеличить на 1, в зависимости от остатка от деления n на 3.
Возможный правильный ответ:
ЧВХ
ЧЧЧВВВХХХ
ЧЧЧЧВВВХХХХ
ЧЧЧЧВВВВХХХХХ
Задача 3. Кратчайший путь
Можно начать с любого города и выбирать на каждом шаге ещё не посещённый город с мини-
мальной стоимостью перелёта. Получится маршрут «AEDCGFB», при этом в конце этого маршру-
та будут выбраны уже довольно дорогие перелёты. Стоимость такого маршрута равна 27. Дальше
можно начать перебирать различные варианты продолжения, заменяя дешёвые перелёты на более
дорогие, в расчёте, что в дальнейшем удастся использовать рейсы меньшей стоимости.
Лучший ответ имеет вид «ABDEFCG», стоимость этого маршрута равна 24.
Задача 4. Путешествие
Добавим в таблицу две строки. В строке 1 будем записывать заголовки столбцов. В строке 2
в ячейках B2 и С2 запишем нули - координаты начальной точки. В последующих 1000 строках
столбцов B и C запишем координаты точки, в которой окажется Данис после выполнения очередного
шага.
Для этого нам нужно в каждой строке с 3 по 1002 записать формулы в столбцах B и C, учи-
тывающие координаты в предыдущей строке и команду перемещения, записанную в столбце A - к
каждой из координат нужно прибавить одно из трёх чисел 0, 1, -1 в зависимости от команды. Напри-
мер, в ячейку B3 записать формулу =B2+IFS(A3="направо";1;A3="налево";-1;TRUE();0),
в ячейку C3 записать формулу =C2+IFS(A3="вверх";1;A3="вниз";-1;TRUE();0), скопиро-
вать эти две ячейки в блок B4:C1002.
Ответ на первый вопрос можно найти при помощи формулы или фильтра. Зададим фильтр в
столбце B по значению -11 и в столбце C по значению 9. Будет отфильтровано 9 строк, это и есть
ответ на первое задание.
Чтобы ответить на второй вопрос, необходимо посчитать количество различных значений в
столбцах B и C. Однако, работать с парами чисел трудно, удобно работать с одним числом. Для
каждой точки в столбце D запишем уникальное число, которое будет различать координаты. Для
этого можно использовать формулу =B2 ∗ 100 + C2, которую мы запишем в ячейку D2 и скопи-
руем в блок D3:D1002. Здесь мы воспользуемся тем, что все координаты, как можно заметить, по
модулю будут меньше 50.
Далее нужно посчитать количество уникальных чисел в столбце D. В Excel это можно сделать
при помощи функции «Удалить дубликаты», в LibreOffice Calc есть параметр фильтра «Без по-
вторений». Мы же рассмотрим решение, не использующее специальные возможности конкретных
приложений. Для каждого посещения точки вычислим в столбце E последовательный номер это-
го посещения (то есть для первого посещения точки запишем 1, при повторном посещении этой
точки запишем 2 и т.д.). В ячейку E2 запишем формулу =COUNTIF($D$2:D2;D2). Обратите
внимание на абсолютную адресацию в формуле: это подсчёт значений, равных D2, среди значений в
этом столбце, находящихся выше этой ячейки. Скопируем эту формулу в блок E3:E1002. Тогда при
первом заходе в данную точку в соответствующей ячейке таблицы будет записано число 1. Нужно
посчитать количество ячеек столбца E, в которых записано число 1. Это можно сделать функцией
COUNTIF или при помощи фильтра. Количество таких ячеек будет 383.
Чтобы ответить на третий вопрос, нужно найти точку, которой соответствует максимальное
значение в столбце E. Это тоже удобно делать при помощи фильтра. Максимальное значение в
Страница 2 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
столбце E равно 12, отфильтровав строки в столбце E по числу 12, получим единственную строку.
Координаты этой точки равны (-14; 4).
Наконец, посчитаем расстояние от каждой точки маршрута до точки (10;6). Запишем в ячейку
F2 формулу =ABS(B2-10) + ABS(C2-6) и скопируем её в блок F3:F1002. Снова воспользуемся
фильтром, на этот раз по столбцу F. Минимальное значение в столбце F составит 10 и оно будет
достигаться в точке (1; 7) (причём эта точка будет посещена дважды). Это и есть ответ на последнее
задание.
Задача 5. Качели
Первую группу тестов можно пройти при помощи переборного решения. Будем перебирать зна-
чение ответа (массу камня) в переменной 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
or
abs ( a+b-c+ans ) <= d
or abs ( b+c-a-ans ) <= d
or
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 ) )
Задача 6. Фонари
Вывод программы различается для случаев, когда размещение фонарей возможно или невоз-
можно. Один фонарь первого типа освещает 2x + 1 домов, второго типа - 2y + 1 домов. Поэтому
сначала проверим, существует ли решение задачи, то есть посчитаем максимальное число домов,
которые могут освещаться a фонарями первого вида и b фонарями второго вида. Если это число
меньше n, то нужно вывести -1. Иначе получим ответ при помощи «жадного» алгоритма: для
Страница 3 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
минимизации числа фонарей выберем фонарь, который освещает больше домов, и разместим его
так, чтобы множество домов, которое он освещает, непосредственно примыкало к уже освещённым
домам. Повторим этот процесс, пока все дома не станут освещены.
В приведённом ниже решении мы предполагаем, что фонари первого вида освещают большее
число домов, то есть x y. Если это не так, то поменяем два вида фонарей местами. Поэтому
будем стараться всегда использовать фонарь первого вида. В переменной last_lighted хранится
номер последнего освещённого дома. Цикл продолжается, пока не все дома освещены, то есть пока
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
Задача 7. Деление шоколадки
Должен получиться большой кусок и ещё 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 ( ) )
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 )
Страница 4 из 5
Школьный этап всероcсийской олимпиады по информатике для 7-8 классов
22 октября 2024
Чтобы набрать 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 из 5
Школьный этап всероcсийской олимпиады по информатике для 9-11 классов
22 октября 2024
Задача 1. Качели
Ограничение по времени:
0.5 секунд
Трое друзей - Аня, Боря и Саш - пришли на детскую площадку, чтобы покачаться на качелях-
балансире. Качели представляют собой длинную балку, закреплённую в центре, на которую дети
садятся с разных концов.
Массы детей равны A, B и C кг. Чтобы держать баланс на качелях, разница масс на двух
концах качелей должна быть не более D кг. Друзьям повезло: рядом с площадкой оказалась груда
достаточно тяжёлых камней. Один из детей может взять с собой любой камень, чтобы сделать
разность масс на концах качелей допустимой. Помогите друзьям определить минимальную массу
камня, благодаря которому они смогут покачаться на качелях.
Формат входных данных
Программа получает на вход три числа A, B, C, записанных в отдельных строках, - массы
друзей. В четвёртой строке записано число D - наибольшая допустимая разница масс на концах
качелей. Все числа - целые, положительные и не превосходящие 109.
Формат выходных данных
Программа должна вывести одно целое число - минимальную необходимую массу камня, ко-
торую нужно добавить на одну из сторон качелей, чтобы друзья смогли покачаться на них, сев
оптимально. Если камень им не понадобится, программа должна вывести число 0.
Система оценки
Решения, правильно работающие, когда все входные числа не превосходят 105, будут оцениваться
в 40 баллов.
Примеры
стандартный ввод
стандартный вывод
30
15
40
35
10
30
0
20
45
10
Замечание
В первом примере Аня и Саша сядут на одну сторону, их суммарная масса будет равна 65 кг. На
другую сторону сядет Боря, взяв 15-килограммовый камень, тогда масса Бори с камнем составит
55 кг. Разница весов на концах качелей примет значение 10 кг.
Во втором примере Аня и Боря сядут на одну сторону (50 кг), Саша - на другую сторону (45 кг).
Разница весов будет равна 5 кг, поэтому камень не понадобится.
Страница 1 из 6
Школьный этап всероcсийской олимпиады по информатике для 9-11 классов
22 октября 2024
Задача 2. Фонари
Ограничение по времени:
1 секунда
Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние
между домами за единицу длины.
Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут
освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на
расстоянии Y (включительно). В частности, при X = 0 или Y = 0 такой фонарь освещает только
тот дом, у которого он установлен.
Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены.
Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами
необязательно.
Формат входных данных
Первая строка входных данных содержит целое число N (1 N
105). Следующие четыре
строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосхо-
дят 105.
Формат выходных данных
Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая
строка должна содержать два целых числа черезпробел - координату фонаря и расстояние,которое
он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1
до N, рядом с каждым домом можно поставить только один фонарь.
При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не
существует, программа должна вывести одно число -1.
Система оценки
Решения, правильно работающие при A = 0 или B = 0, будут оцениваться в 30 баллов.
Решения, правильно работающие при A /= 0, B /= 0, n
1000, будут оцениваться в 40
баллов.
Примеры
стандартный ввод
стандартный вывод
10
2 1
3
5 2
1
9 1
1
2
10
-1
1
1
1
2
Замечание
В ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 -
также дома 3, 4, 6 и 7, а фонарь у дома 9 - также дома 8 и 10. В результате все дома освещены.
Во втором примере фонарей недостаточно.
Страница 2 из 6

 

 

 

 

 

 

 

 

содержание      ..      1       2         ..

 

//////////////////////////////////////////