Школьный этап, 5–6 классы всероссийской олимпиады по информатике: 5 задач с официальным разбором.
К задаче 1Школьный этап ВсОШ по информатике 2024/25, 5–6 классы.
Задачи тура
- 1Квадратматематика, жадный алгоритм
- 2Переправаперебор, графы
- 3Чаепитиематематика, инверсии
- 4Набор на кружкиматематика, множества
- 5Кратчайший поездконструктив, перебор
Отмечайте решённые: 0 из 5
1. Квадрат
В квадрате расставили числа от 1 до 9. Затем внутри этого квадрата взяли все квадраты и посчитали сумму чисел в каждом их них, а потом сложили все полученные суммы.
Расставьте числа от 1 до 9 в квадрате так, чтобы полученная сумма была как можно больше. Каждое из чисел от 1 до 9 должно встречаться в вашем ответе ровно один раз.
В ответе запишите 3 строки, в каждой строке должно быть 3 числа через пробел.
Официальный разборСначала попробуйте решить сами
Официальный разбор
Центральная клетка принадлежит четырём квадратам , четыре клетки посередине сторон — двум квадратам каждая, а клетки в углах — только одному квадрату. Поэтому в центре должно стоять число 9, а в углах — числа 1, 2, 3, 4. На серединах сторон должны стоять числа 5, 6, 7, 8. Любой ответ, соответствующий этим условиям, будет правильным.
1 5 2
6 9 7
3 8 42. Переправа
Семье из мамы и пяти детей в возрасте 5, 6, 7, 8 и 9 лет нужно переправиться через реку, с левого берега на правый. У них есть лодка, которая может вместить маму (которая обязательно должна плыть в лодке) и не более, чем двух детей.
Если на берегу без мамы останутся два ребёнка, возраст которых отличается на 1 год (то есть 5 и 6 лет или 6 и 7 лет и т.д.), то они подерутся. Составьте план переправы через реку так, чтобы никто не подрался.
Запишите несколько строк, каждая из которых содержит одно или два числа, соответствующие возрасту детей (то есть одно или два числа из множества 5, 6, 7, 8, 9). Мама переплывает реку на каждом шаге. Если мама переплывает реку без детей, напишите в этой строке знак «-».
Нечётные строки соответствуют перемещению лодки с левого берега на правый, чётные строки — в противоположном направлении.
Чем меньше строк будет в вашем ответе, тем больше баллов вы получите.
Официальный разборСначала попробуйте решить сами
Официальный разбор
Сначала нужно перевезти детей 6 и 8 лет, это единственный способ оставить на левом берегу троих (5, 7 и 9 лет) так, чтобы избежать конфликта. Затем мама должна вернуться назад и перевезти любых двоих из оставшихся на левом берегу детей, но обратно ей придётся вернуться с детьми 6 и 8 лет. Их она оставит на левом берегу, перевезёт того оставшегося ребёнка, который ждёт на левом берегу с самого начала, вернётся и заберёт детей 6 и 8 лет. Пример такого решения.
6 8
-
5 9
6 8
7
-
6 83. Чаепитие
Слон Семён каждое утро пьёт чай и ест бутерброды с яблочным вареньем. У него есть длинный стол, на котором в ряд слева направо выставлены чашки чая и банки с вареньем и выложен хлеб. Чтобы чаепитие удалось, нужно, чтобы при просмотре слева направо сначала шёл весь хлеб, затем всё варенье, и затем весь чай.
Слон использует хобот для перестановки предметов, поэтому за одну секунду он может поменять местами только два соседних предмета. Обозначим хлеб буквой «Х», варенье буквой «В», чай буквой «Ч». Тогда последовательность предметов на столе задаётся строкой из этих букв. Например, при расстановке предметов «ВЧХВ» на подготовку стола потребуются три секунды. Предметы, которые переставляются местами каждую секунду, подчёркнуты.
1. ВХЧВ
2. ХВЧВ
3. ХВВЧ
Слон торопится, и поэтому хочет знать, при какой первоначальной расстановке предметов у него уйдёт наибольшее время на подготовку стола.
Вам нужно дать ответ для четырёх случаев: когда на столе у Семёна стоит 3, 6, 7 и 8 предметов. Для каждого из этих случаев вы должны записать в ответе строку, состоящую из необходимого количества букв, каждая буква должна быть одной из букв «Х», «В», «Ч». Количество предметов каждого вида вы можете выбрать самостоятельно, но общее число букв в ответе должно быть равно 3, 6, 7 и 8. Вы должны найти такую расстановку предметов, при которой подготовка стола займёт наибольшее время для данного числа предметов.
В ответе напишите четыре строки, в первой строке ответ для 3 предметов, во второй строке — для 6 предметов, в третьей строке — для 7 предметов, в четвёртой строке — для 8 предметов. Вы должны записать в ответе 4 строки, если вы не можете найти ответ для какого-то случая, напишите любую строку из букв «Х», «В», «Ч» нужной длины.
Официальный разборСначала попробуйте решить сами
Официальный разбор
Для чаепития необходима такая расстановка предметов: Х, ..., Х, В, ..., В, Ч, ...Ч. Нам необходимо получить перестановку предметов, для которой получение такой последовательности потребовало бы как можно больше операций. Поэтому в ответе не могут идти буквы Х и В подряд, иначе, переставив их местами, мы получим большее число операций. Также подряд не могут идти буквы В и Ч. То есть ответ всегда имеет вид Ч, ..., Ч, В, ..., В, Х, ..., Х. Осталось только понять, сколько нужно взять чая, варенья и хлеба в ответе.
Пусть в ответе чай встречается раз, варенье встречается раз, хлеб встречается раз, . Посчитаем количество секунд, необходимых для приведения такой перестановки в порядок. Нам придётся поменять местами каждую порцию чая и варенья, это займёт секунд. Аналогично понадобится секунд, чтобы поменять варенье и хлеб и секунд, чтобы поменять чай и хлеб. Нужно подобрать такие значения , , , чтобы сумма была максимальной.
Интуитивно понятно, что числа должны быть равны или близки (отличаться на 1). Докажем это. Пусть, например, числа и отличаются на 2 и более, то есть . Рассмотрим новую последовательность, в которой будет на 1 меньше, а увеличим на 1. Тогда для новой последовательности ответ равен , то есть ответ изменится на , и если , то продолжительность увеличится. Таким образом, в правильном ответе среди чисел , , не должно быть различающихся на 2 и более.
Итак, если делится на 3, то необходимо взять . Если не делится на 3, то одно или два из этих чисел нужно увеличить на 1, в зависимости от остатка от деления на 3.
Возможный правильный ответ:
ЧВХ
ЧЧВВХХ
ЧЧВВХХХ
ЧЧЧВВХХХ4. Набор на кружки
Учащиеся школы должны выбрать себе дополнительные занятия на год. Каждый из них выбрал как минимум один предмет из предложенных: биологии, музыки и шахмат. Известно, что 150 школьников выбрали биологию, 130 учеников — музыку и 100 — шахматы, но каждый учащийся мог выбрать и несколько предметов.
Ответьте на вопросы:
1. Какое минимальное количество учащихся могло быть в школе?
2. Какое максимальное количество учащихся могло быть в школе?
3. Считайте, что одновременно биологию и музыку выбрали 85 учащихся. Сколько школьников выбрало ровно один из этих двух предметов?
4. Считайте, что ни один школьник не выбрал одновременно биологию и шахматы, одновременно биологию и музыку выбрали 60 человек, а всего в школе 250 учащихся. Сколько школьников выбрало и шахматы, и музыку?
5. Считайте, что в ситуации из пункта 4 на кружки разрешили записываться учащимся других школ. Какое минимальное дополнительное количество школьников должно записаться на предложенные предметы, чтобы количество людей, посещающих только музыку, стало равняться количеству людей, не посещающих её?
В ответе запишите пять целых чисел, каждое число — в отдельной строке. Если вы не можете дать ответ на какой-то вопрос, запишите в ответе любое число.
Официальный разборСначала попробуйте решить сами
Официальный разбор
1. Так как 150 школьников выбрали биологию, количество учеников в школе не может быть меньше 150. Но оно может быть равно 150, если все ученики будут выбирать биологию и ещё одно или два дополнительных занятия.
2. Наибольшее число учеников в школе окажется в случае, если все выбрали разные занятия. Тогда число учеников будет равно .
3. Если и биологию, и музыку выбрали 85 учащихся, то только биологию выбрали учащихся, только музыку выбрали , а ровно один из этих предметов выбрали школьников.
4. Поскольку из 250 учащихся биологию выбрали 100 учащихся, шахматы 150, и никто не выбрал и шахматы, и биологию одновременно, то каждый учащийся обязательно выбрал или биологию, или шахматы, то есть нет учащихся, выбравших только музыку. Каждый учащийся, выбравший музыку, выбрал ещё один предмет. При этом музыку и биологию выбрали 60 учащихся, значит, музыку и шахматы выбрали учащихся.
5. В предыдущем пункте музыку посещают 130 человек, а не посещают человек, при этом только музыку не посещает никто. Чтобы число учеников, посещающих только музыку, стало равным числу учеников, не посещающих музыку, необходимо, чтобы 120 новых школьников записались только на музыку.
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).
В ответ запишите последовательность букв, обозначающих вагоны. Чем короче будет ваш ответ, тем больше баллов вы получите.
Официальный разборСначала попробуйте решить сами
Официальный разбор
Рассмотрим сцепку из вагонов FVGVF. Она удовлетворяет условиям размещения грузовых вагонов и вагонов с ценностями рядом с вагонами охраны и содержит два грузовых вагона и два вагона с ценностями. Нам необходимо использовать две такие сцепки, а ещё в одной сцепке оставить только один вагон с ценностями и один грузовой вагон. Между сцепками вставим локомотивы, получим такое решение:
LFVGVFLFVGVFLGVFLВ этом решении мы использовали минимальное число вагонов охраны, но количество локомотивов можно сократить. Поставим в центр один локомотив, одну сцепку разместим в начале поезда, ещё одну сцепку — в конце. Нам осталось разместить ещё один грузовой вагон и вагон с ценностями, также нам понадобится один вагон охраны. Поскольку длина сцепки равна 5, а подряд могут идти 7 вагонов без локомотива, то слева и справа от центрального локомотива можно разместить ещё по два вагона с каждой стороны. Разместим в центре конструкцию FLGV. Она удовлетворяет условию размещения грузовых вагонов и вагонов с ценностями, и в итоге мы обошлись только одним дополнительным локомотивом. Возможный ответ:
LFVGVFFLGVFVGVFLСначала решите сами
Возьмите столько времени, сколько было на олимпиаде, и только потом открывайте разбор.
Другие туры
2026/27
- Школьный этап, 9–11 классы5 задач
- Школьный этап, 7–8 классы6 задач
- Школьный этап, 5–6 классы5 задач
2025/26
- Школьный этап, 9–11 классы5 задач
- Школьный этап, 7–8 классы6 задач
- Школьный этап, 5–6 классы5 задач
- Муниципальный этап, 9–11 классы5 задач
- Муниципальный этап, 7–8 классы6 задач
2024/25
- Школьный этап, 9–11 классы5 задач
- Школьный этап, 7–8 классы7 задач
- Школьный этап, 5–6 классы5 задач
- Муниципальный этап, 9–11 классы5 задач
- Муниципальный этап, 7–8 классы7 задач
2023/24
- Школьный этап, 9–11 классы5 задач
- Школьный этап, 7–8 классы7 задач
- Школьный этап, 5–6 классы5 задач
- Муниципальный этап, 9–11 классы5 задач
- Муниципальный этап, 7–8 классы7 задач