Олимпиада по информатике 4–5 классы — пригласительный этап ВсОШ 2024/2025: задания и ответы
Официальный комплект пригласительного этапа Всероссийской олимпиады школьников по информатике для 4–5 классов (2024/2025 учебный год). Задания и решения с критериями оценивания — скачайте PDF или прорешайте онлайн по тексту ниже.
Задания — текст для прорешивания
Текст извлечён из официального PDF автоматически: формулы, таблицы и рисунки могут отображаться неточно — сверяйтесь с документом выше.
Пригласительный этап всеро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 баллов.
Примеры стандартный ввод
стандартный вывод
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 12
3 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 0
15
9 15 4
11
9 15 7
9 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 2 110001
5 3
6 3 010010
1 6 3
Замечание В первом примере первоначально заняты места 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 001100
1 0
Замечание В первом примере из условия подходят следующие подстроки (выделены жирным): 001100, 001100, 001100, 001100, 001100, 001100, 001100.
Страница 7 из 7
Ответы и решения — показать
Официальные ответы и критерии оценивания жюри. Сначала решите задания самостоятельно.
Пригласительный этап всеро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