Школьный этап, 7–8 классы всероссийской олимпиады по информатике: 7 задач с официальным разбором, к 3 из них наше решение на C++.

Школьный этап ВсОШ по информатике 2023/24, 7–8 классы.

Москва, 24 октября 2023Условия PDF Разбор PDF Архив с тестами Видеоразбор

Задачи тура

1Защитный экранперебор, математика
2Гоночная трассамоделирование, поиск в ширину
3Бег по пересечённой местностиграфы, конструктив
4Конференцияжадный алгоритм, электронные таблицы
5Пара-тройка конфетматематика
6Речной бойматематика
7Сломанный индикатормножества, реализация

Отмечайте решённые: 0 из 7

1. Защитный экран

перебор, математика

В радиологической лаборатории во время экспериментов используются защитные свинцовые экраны. В зависимости от расстояния, на которое излучение может проникнуть в материал (проникающей способности), подбирается экран из одной или нескольких свинцовых пластин толщиной от 1 до 100 сантиметров.

В лаборатории есть семь пластин толщиной 32, 3, 37, 8, 2, 17, 1 сантиметров. В сумме они дают ровно 100 сантиметров. Сотрудники планируют провести эксперимент с новым видом излучения, проникающая способность которого неизвестна, то есть им необходимо собрать из имеющихся пластин экран некоторой толщины от 1 до 100 сантиметров.

Определите все возможные значения проникающей способности излучения, для которых не удастся собрать защитный экран нужной толщины, используя имеющиеся в лаборатории пластины. Каждое значение записывайте в отдельное поле, добавляя их по мере необходимости. В ответе укажите несколько чисел (единицу измерения указывать не нужно), добавляя поля ввода по мере необходимости.

Официальный разборСначала попробуйте решить сами

2. Гоночная трасса

моделирование, поиск в ширину

Гоночная трасса имеет форму, изображённую на рисунке.

Гоночный автомобиль выезжает из левого верхнего угла трассы и за первую минуту перемещается на 1 клетку вправо. Далее за каждую последующую минуту автомобиль перемещается на целое число клеток по прямой в одном направлении. Каждую минуту автомобиль может изменять скорость не более чем на 1, то есть за каждую минуту автомобиль проезжает столько же клеток, сколько за предыдущую минуту, или на одну клетку больше или на одну клетку меньше. Поскольку каждое перемещение выполняется по прямой, в тех клетках, в которых происходит поворот трассы, должно закончиться очередное перемещение автомобиля.

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

В ответе запишите последовательность чисел, соответствующую перемещению автомобиля каждую минуту. Каждые два соседних числа в последовательности должны отличаться не более, чем на 1, первое и последнее число должны быть равны 1. Каждое значение записывайте в отдельное поле, добавляя их по мере необходимости. Чем меньше чисел будет в вашем ответе, тем больше баллов вы получите (при условии, что последовательность перемещений будет удовлетворять всем необходимым условиям).

Например, если трасса имела бы такой вид, как на рисунке справа, то в ответе необходимо записать числа 1, 2, 2, 2, 1, 1, 1. На рисунке эти числа записаны в конечных клетках соответствующего перемещения.

Официальный разборСначала попробуйте решить сами

3. Бег по пересечённой местности

графы, конструктив

Участникам соревнования по бегу по пересечённой местности необходимо преодолеть маршрут из левого верхнего угла в правый нижний угол участка, состоящего из $8 \times 8$ клеток. Участник может перемещаться из клетки в одну из четырёх клеток, имеющих общую сторону с клеткой, где он находится в данный момент, не выходя при этом за границу квадрата. На рисунке изображён вид участка и один из возможных маршрутов бегуна. Участники всегда выбирают кратчайший маршрут.

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

В ответе запишите 8 строк по 8 символов «.» и «#», где символ «.» означает пустую клетку, а символ «#» — клетку с препятствием. Левый верхний и правый нижний углы вашего ответа должны быть свободными, также должен существовать маршрут из левого верхнего в правый нижний угол.

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

Официальный разборСначала попробуйте решить сами

4. Конференция

жадный алгоритм, электронные таблицы

Для выступления на очень важной конференции подали заявки 1000 докладчиков. Каждый из них готов сделать доклад строго в указанное время, но одновременно может выступать только один докладчик, поэтому удовлетворить все заявки невозможно.

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

Данные для выполнения этого задания находятся в файле электронной таблицы.

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

Файл содержит три колонки. В колонке A указан номер докладчика от 1 до 1000, в колонках B и C указаны желаемые времена начала и окончания доклада в формате времени электронной таблицы. Количество секунд во всех временах равно нулю.

В ответ запишите номера докладчиков (числа от 1 до 1000), которых вы выберете для выступления на конференции. Каждое число записывайте в отдельное поле ввода, добавляя поля по мере необходимости. Времена выступлений выбранных докладчиков не должны пересекаться. Чем больше докладов вы выберете, тем больше баллов получите (при условии, что предложенный вами набор докладчиков удовлетворяет условию задачи).

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

Официальный разборСначала попробуйте решить сами

Официальный разбор

Ответ: 249, 296, 468, 512, 523, 640, 777, 799, 804, 819, 855, 876, 915

Задача решается про помощи «жадного алгоритма». Выберем докладчика, которых хочет закончить свой доклад раньше всех. Вторым выберем докладчика, который готов закончить раньше всех из тех докладчиков, которые выступают после первого. Затем выберем докладчика, который заканчивает раньше всех из тех, кто начинает после второго выбранного и т.д.

Для реализации этого решения отсортируем входные данные по столбцу C, то есть по времени окончания доклада. Теперь в ячейку D2 запишем формулу =IF(B2>=MAX($D$1:D1);C2;""). Эта формула запишет в ячейку время окончания выступления этого докладчика (C2), если время начала его выступления (B2) не меньше, чем максимальное время выступления ранее выбранных докладчиков (формула с функцией MAX), иначе это будет пустая строка. Затем эту формулу скопируем в ячейки D3:D1001. Тем самым для докладчиков, которых мы выберем, в столбце D будет записано время окончания их выступления, а для остальных докладчиков — пустая строка.

Осталось только при помощи фильтра выбрать строки с непустыми значениями в столбце D и взять из столбца A номера выбранных докладчиков.

Ответ: 249, 296, 468, 512, 523, 640, 777, 799, 804, 819, 855, 876, 915. Возможны и другие варианты ответа, в лучшем решении выбраны 13 докладчиков.

5. Пара-тройка конфет

1 секунда, математика

У Алисы сегодня день рождения, и она хочет угостить своих одноклассников конфетами. В магазине, в который она успеет зайти перед школой, есть сладости двух видов: шоколадные и карамельные. Они продаются наборами по 3 штуки, причем в упаковке есть конфеты каждого из двух видов (то есть в одной упаковке лежат две конфеты одного вида и одна конфета другого вида). По внешнему виду упаковки нельзя понять, какие конфеты лежат внутри.

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

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

В единственной строке задано число $n$ ( $1 ⩽ n ⩽ 1 0^{9}$ ) — количество человек в классе.

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

Выведите единственное число — количество упаковок, которое должна купить Алиса.

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

Решения, правильно работающие при $n ⩽ 1 0^{3}$ , будут оцениваться в 25 баллов.

Решения, правильно работающие при $n ⩽ 1 0^{6}$ , будут оцениваться в 50 баллов.

Замечание

В первом примере Алиса купит две упаковки с конфетами. В первой упаковке лежат 2 конфеты одного вида, и 1 конфета другого вида. Если вторая упаковка будет такая же, как и первая, то у Алисы окажется 4 конфеты одного вида и 2 конфеты другого вида. Если вторая упаковка будет отличаться от первой, то у Алисы будет по 3 конфеты каждого вида. В любом случае у Алисы найдётся 3 конфеты одного вида.

Как видно из первого примера, для того, чтобы гарантированно получить 4 конфеты одного вида, недостаточно купить две упаковки.

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

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

Официальный разборСначала попробуйте решить сами

Наше решение на C++Полный код на C++17

Официальный разбор

Заметим, что упаковки конфет могут быть двух типов: с двумя шоколадными + одной карамельной или одной шоколадной + двумя карамельными. Также заметим, что ответ не превосходит $n$ , так как в каждой упаковке есть хотя бы одна конфета каждого вида.

При $n ⩽ 1 0^{3}$ можно перебрать количество купленных коробок и убедиться, что при любом распределении конфет в купленных упаковках найдётся не менее $n$ конфет одного вида.

Пусть $k$ — количество купленных коробок, из них $k_{1}$ — первого типа (две шоколадные и одна карамельная), тогда $k_{2} = k - k_{1}$ — число коробок второго типа (одна шоколадная и две карамельные). Конфет одного вида будет $max (2 k_{1} + k_{2}, k_{1} + 2 k_{2})$ . Для выбранного $k$ переберём значения $k_{1}$ такие, что $0 ⩽ k_{1} ⩽ k$ и если для всех $k_{1}$ верно, что $max (2 k_{1} + k_{2}, k_{1} + 2 k_{2}) ⩾ n$ , то данное значение $k$ подходит. Минимальное подходящее $k$ является ответом.

Такое решение имеет сложность $O (n^{2})$ и набирает 25 баллов. Пример такого решения.

solution.py

n = int(input())
k = 1
ok = False
while not ok:
    ok = True
    for k1 in range(k + 1):
        k2 = k - k1
        if max(2 * k1 + k2, k1 + 2 * k2) < n:
            ok = False
    k += 1
print(k - 1)

При $n ⩽ 1 0^{6}$ всё ещё получится перебирать значения $k$ , но необходимо избавиться от вложенного цикла, перебирающего возможное распределение упаковок. Заметим, что в худшем случае (чтобы минимизировать количество конфет одного вида), значение $k_{1} \approx k_{2}$ , то есть конфет каждого вида окажется примерно поровну.

Заметим, что в двух упаковках точно найдётся три конфеты одного вида. Если мы покупаем чётное число $k$ упаковок, то среди них точно будет $3 k /2$ конфет одного вида. Если $k$ нечетное, то количество конфет одного вида будет не меньше, чем $⌊ 3 k /2 ⌋ + 2$ . Переберём значения $k$ , пока не найдём минимальное подходящее.

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

solution.py

n = int(input())
k = 0
while k // 2 * 3 + (k % 2) * 2 < n:
    k += 1
print(k)

Полное решение имеет сложность $O (1)$ . Если $n$ делится на 3, то нужно купить $2 n /3$ упаковок (в каждых двух упаковках есть три конфеты одного вида). Если же купить на одну упаковку больше, то в лишней упаковке окажутся 2 одинаковые конфеты. Поэтому для тех значений $n$ , которые не делятся на 3, нужно будет купить ещё одну дополнительную упаковку.

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

solution.py

n = int(input())
if n % 3 == 0:
    print(n // 3 * 2)
else:
    print(n // 3 * 2 + 1)

Наше решение на C++

solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    long long answer = n / 3 * 2;
    if (n % 3 != 0) answer += 1;
    cout << answer << "\n";
    return 0;
}

6. Речной бой

1 секунда, математика

Поле в игре «Речной бой» представляет собой полоску длины $n$ клеток и шириной в одну клетку. Где-то на поле расположен корабль из $k$ клеток ( $k ⩽ n$ ). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: «мимо», «ранен» или «убит».

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

Первая строка входных данных содержит целое число $n$ ( $1 ⩽ n ⩽ 1 0^{9}$ ).

Вторая строка входных данных содержит целое число $k$ ( $1 ⩽ k ⩽ n$ ).

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

Выведите одно целое число — количество выстрелов.

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

Решения, правильно работающие при $n ⩽ 10$ , будут оцениваться в 40 баллов.

Замечание

В первом примере поле состоит из $n = 4$ клеток, корабль имеет длину $k = 2$ . Первый выстрел нужно сделать в одну из двух центральных клеток. Если результатом будет «ранен», то вторая клетка корабля находится в одной из двух соседних клеток, и за два выстрела мы гарантированно потопим корабль Если результатом первого выстрела будет «мимо», то корабль занимает две единственные свободные смежные клетки, которые тоже можно подбить двумя выстрелами. Итого нужно 3 выстрела. Двух выстрелов недостаточно, так как всегда есть шанс промахнуться первым выстрелом.

стандартный ввод	стандартный вывод
4 2	3

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

Официальный разборСначала попробуйте решить сами

Наше решение на C++Полный код на C++17

Официальный разбор

Будем стрелять последовательно так, чтобы не пропустить корабль. Для этого нужно стрелять, оставляя между выстрелами $k - 1$ пустую клетку, то есть в клетки с номерами $k$ , $2 k$ , $3 k$ и т.д., до тех пор, пока не получим результат «ранен», либо такие клетки не кончатся. Мы сделаем не более, чем $⌊ n / k ⌋$ выстрелов (целочисленное частное от деления $n$ на $k$ ). Получив на каком-то выстреле ответ «ранен», начнём стрелять в соседние клетки в одну сторону, а при получении результата «мимо» — в другую сторону. Тем самым мы сделаем не более одного дополнительного промаха, то есть для попадания в $k - 1$ клетку корабля понадобятся не более $k$ выстрелов, и общее число выстрелов будет равно $⌊ n / k ⌋ + k$ .

Но если $n$ делится на $k$ , то последний выстрел из первой последовательности придётся в последнюю клетку поля, и тогда с одной стороны от этой клетки больше не останется клеток. В этом случае достаточно только $k - 1$ дополнительных выстрелов, то есть при $n$ , делящемся на $k$ , ответ равен $⌊ n / k ⌋ + k - 1$ .

Используя целочисленное деление, оба этих случая можно записать одной формулой.

solution.py

n = int(input())
k = int(input())
print((n - 1) // k + k)

Наше решение на C++

solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, k;
    cin >> n >> k;
    cout << (n - 1) / k + k << "\n";
    return 0;
}

7. Сломанный индикатор

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

У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор, который может показывать цифры от 0 до 9 в виде цифр «почтового индекса» (см. рисунок):

Цифры 0–9 на девятисегментном индикаторе

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

Алексей уже выяснил, что индикатор всё ещё способен показать какие-то $n$ цифр. Однако радиолюбитель не может проверить остальные цифры, равно как и каждый сегмент отдельно. Поэтому он просит вас помочь найти те цифры, которые гарантированно можно показать на этом индикаторе.

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

Первая строка входных данных содержит число $n$ ( $1 ⩽ n ⩽ 10$ ) — количество цифр, которые смог показать на индикаторе Алексей.

Следующие $n$ строк содержат по одной цифре $a_{i}$ ( $0 ⩽ a_{i} ⩽ 9$ ) — сами цифры, которые Алексей смог показать. Гарантируется, что все $a_{i}$ различны.

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

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

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

Решения, правильно работающие при $2 ⩽ a_{i} ⩽ 4$ , будут оцениваться в 28 баллов.

стандартный ввод	стандартный вывод
3 2 4 8	0 2 4 5 8 9

стандартный ввод	стандартный вывод
2 6 1	1 6

Официальный разборСначала попробуйте решить сами

Наше решение на C++Полный код на C++17

Официальный разбор

Для начала формализуем условие задачи. Некий индикатор состоит из 9 сегментов, каждый из которых либо гарантированно работает (зажигается какой-то цифрой из данного набора), либо имеет неизвестное состояние (не зажигается ни одной из данных цифр). Задача заключается в нахождении всех цифр, которые состоят только из гарантированно рабочих индикаторов.

Пронумеруем сегменты индикатора сверху вниз, слева направо, то есть самый верхний сегмент будет иметь номер 1, а самый нижний — 9. Для каждой возможной цифры перечислим сегменты, из которой она состоит. Например, цифра 0 состоит из сегментов 1, 2, 4, 6, 8, 9.

Если какая-то цифра могла быть отображена на экране, то соответствующие ей сегменты заведомо исправны. Если несколько цифр могли быть отображены на экране, то исправны сегменты, которые входят в хотя бы одну данную цифру. То есть нужно сделать объединение множеств сегментов, соответствующих данным цифрам. Это удобно реализовать при помощи структуры данных «множество» в языке Python, но можно использовать и массивы из нулей и единиц (где единица будет соответствовать исправному сегменту индикатора) или битовые операции, но тогда реализация станет сложнее.

Для проверки, что какую-то цифру гарантированно удастся показать на индикаторе, множество сегментов этой цифры должно быть подмножеством заведомо исправных сегментов. Для этого в Python есть операция <= для множеств.

Приведём пример решения на языке Python. Здесь segments — это список множеств, соответствующих цифрам, то есть segments[i] — это список сегментов, входящих в цифру $i$ .

После нахождения объединения множеств сегментов переберём все цифры от 0 до 9 и выведем подходящие из них.

solution.py

segments = [
    {1, 2, 4, 6, 8, 9},
    {3, 4, 8},
    {1, 4, 7, 9},
    {1, 3, 5, 7},
    {2, 4, 5, 8},
    {1, 2, 5, 8, 9},
    {3, 5, 6, 8, 9},
    {1, 3, 6},
    {1, 2, 4, 5, 6, 8, 9},
    {1, 2, 4, 5, 7}]

res = set()
n = int(input())
for i in range(n):
    d = int(input())
    res |= segments[d]

for d in range(0, 10):
    if segments[d] <= res:
        print(d)

Для получения частичного балла при $2 ⩽ a_{i} ⩽ 4$ достаточно было вручную исследовать, какие ответы возникают на 7 возможных тестах этой группы, занести их в программу и выводить нужный ответ в зависимости от ввода.

Наше решение на C++

solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<set<int>> segments = {
        {1, 2, 4, 6, 8, 9},
        {3, 4, 8},
        {1, 4, 7, 9},
        {1, 3, 5, 7},
        {2, 4, 5, 8},
        {1, 2, 5, 8, 9},
        {3, 5, 6, 8, 9},
        {1, 3, 6},
        {1, 2, 4, 5, 6, 8, 9},
        {1, 2, 4, 5, 7}
    };
    int n;
    cin >> n;
    set<int> working;
    for (int i = 0; i < n; i++) {
        int digit;
        cin >> digit;
        working.insert(segments[digit].begin(), segments[digit].end());
    }
    for (int digit = 0; digit < 10; digit++) {
        bool ok = true;
        for (int segment : segments[digit]) {
            if (!working.count(segment)) ok = false;
        }
        if (ok) cout << digit << "\n";
    }
    return 0;
}

Сначала решите сами

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

Другие туры

2026/27

2025/26

2024/25

2023/24

Готовиться самому

Платформа с задачами

1400+ задач с автопроверкой

или

Пробное занятие

Призёр ВсОШ, первое бесплатно

Школьный этап ВсОШ по информатике 2023/24, 7–8 классы. ВсОШ 2023/24

Задачи тура

1. Защитный экран

Официальный разбор

2. Гоночная трасса

Официальный разбор

3. Бег по пересечённой местности

Официальный разбор

4. Конференция

Официальный разбор

5. Пара-тройка конфет

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

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

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

Замечание

Официальный разбор

Наше решение на C++

6. Речной бой

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

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

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

Замечание

Официальный разбор

Наше решение на C++

7. Сломанный индикатор

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

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

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

Официальный разбор

Наше решение на C++

Сначала решите сами

Другие туры

Готовиться самому

Школьный этап ВсОШ по информатике 2023/24, 7–8 классы.