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

Муниципальный этап ВсОШ по информатике 2024/25, 7–8 классы.

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

Задачи тура

1Порядок во всёмжадный алгоритм, строки
2Треугольникикомбинаторика, математика
3Электронное табломатематика, конструктив
490 минутэлектронные таблицы, моделирование
5Очень большая кольцевая линияматематика
6Речные прогулкиматематика, бинарный поиск
7Благоустройствожадный алгоритм

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

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

жадный алгоритм, строки

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

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

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

При этом Вася ничего не хочет зачёркивать, поэтому единственное, что ему остаётся, — это дописать цифры в конец этих чисел. Например, если в тетради записано число 12, то Вася может сделать из него числа 120, 121, 1200, 12999 и т. п., то есть любые числа, которые начинаются с 12, а может и оставить число 12.

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

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

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

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

Ответ: 48 50 67 300 820 820 6300 7010 54600 54600

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

2. Треугольники

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

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

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

Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменную $n$ , операции сложения (обозначаются «+»), вычитания (обозначаются «-»), умножения (обозначаются «*»), деления (обозначаются «/») и круглые скобки. Запись вида 2n для обозначения произведения числа 2 и переменной $n$ некорректна, нужно писать 2 * n.

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

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

n * (2 * n - 8)

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

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

математика, конструктив

Электронное табло состоит из двух цифровых разрядов, то есть с его помощью можно отображать двузначные числа от 00 до 99 (однозначные числа дополняются слева нулём). Табло можно управлять при помощи трёх кнопок.

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

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

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

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

1. 23;

2. 38;

3. 65;

4. 84;

5. 99.

В ответе запишите пять строк: последовательности нажатий, необходимых для получения каждого из данных чисел из числа 00. Каждая строка ответа должна состоять только из символов «+», «−», «∗». Чем короче будет ваша последовательность, тем больше баллов вы получите. Если вы не можете дать ответ на какое-нибудь задание, напишите любую непустую последовательность, удовлетворяющую условию, например «+».

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

4. 90 минут

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

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

«Единый» (57 рублей) — одна поездка на любом виде транспорта;
«90 минут» (85 рублей) — не более одной поездки на метро и любое количество поездок на наземном транспорте в течение не более 90 минут с момента начала первой поездки (между началом поездки и началом первой поездки по тарифу «90 минут» должно пройти не более 90 минут).

Смена тарифа происходит автоматически: при первой поездке списывается 57 рублей, и если следующая поездка была совершена в течение 90 минут, причём это не повторная поездка на метро, то с кошелька списывается 28 рублей (в сумме получается 85 рублей) и карта переключается на тариф «90 минут». Последующие поездки, удовлетворяющие условиям тарифа «90 минут», будут бесплатными. Если очередная поездка будет повторной поездкой на метро или с момента первой поездки прошло более 90 минут, то с карты будет списано 57 рублей по тарифу «Единый», затем, возможно, карта опять переключится на тариф «90 минут» и т. д.

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

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

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

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

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

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

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

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

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

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

Первая поездка на наземном транспорте стоит 57 рублей, при второй поездке на метро билет переключится на тариф «90 минут», и с карты спишется 28 рублей, поэтому третья поездка на наземном транспорте будет бесплатной. Четвёртая поездка на наземном транспорте произойдёт по тарифу «Единый», потому что разница между временем этой поездки (2:00) и временем первой поездки по тарифу «90 минут» (0:20) больше 90 минут. При пятой поездке на наземном транспорте произойдёт переключение на тариф «90 минут», шестая поездка на метро будет бесплатной, седьмая поездка на метро будет по тарифу «Единый», потому что в тарифе «90 минут» уже была поездка на метро. Восьмая поездка на наземном транспорте пройдёт по тарифу «90 минут», потому что разница времён 4:20 и 2:50 составляет ровно 90 минут.

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

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

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

В столбце C посчитаем время поездки в минутах относительно начала для удобства вычисления разности времён двух поездок. Это можно сделать при помощи формулы =LEFT(A2;LEN(A2)-3)*60+RIGHT(A2;2).

Поездки будут разбиваться на группы, соответствующие одному тарифу. Для того чтобы тарифицировать одну поездку, нам нужно знать время первой поездки в этой группе (будем записывать его в столбце D) и количество поездок на метро в этой группе (в столбце E). В следующих двух столбцах будут записаны логические выражения, определяющее вид поездки. В столбце F будем записывать TRUE для первой поездки в группе (то есть для поездок по тарифу 57 рублей), в столбце G будем записывать TRUE для второй поездки по тарифу «90 минут» (то есть для поездок по тарифу 28 рублей). Строку 2 таблицы можно заполнить явно, записав в F2 значение TRUE, а в G2 — FALSE.

Поездка будет оплачена по тарифу «Единый», то есть будет первой поездкой в группе, при выполнении хотя бы одного условия: после времени начала первой поездки предыдущего билета прошло более 90 минут или количество поездок на метро в предыдущем билете вместе с этой поездкой стало больше 1. Поэтому в ячейку C3 можно написать формулу =OR(C3-D2>90;E2+(B3="M")>1).

Поездка будет оплачена по тарифу 28 рублей, если предыдущая поездка была оплачена по тарифу «Единый», а для этой поездки условие оплаты её по тарифу «Единый» не было выполнено. Поэтому в ячейку G3 можно записать формулу =AND(F2;NOT(F3)).

Эти формулы используют данные из столбцов D и E предыдущей строки. Теперь пересчитаем эти значения в текущей строке. Они зависят от того, была ли эта поездка первой поездкой по тарифу, то есть от значения в столбце F. В ячейку D3 запишем формулу =IF(F3;C3;D2), в ячейку E3 запишем формулу =IF(F3;0;E2)+(B3="M").

Наконец, посчитаем стоимость поездки. Она будет равна 57 для поездок, у которых записано TRUE в столбце F, или 28 рублей для поездок, у которых записано TRUE в столбце G. Для вычисления этого значения можно записать формулу =F3*57+G3*28 в ячейку H3.

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

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

0.5 секунд, 256 мегабайт, математика

В Москве построили новую кольцевую линию метро. Она столь большая, что станции на ней не имеют названий, а имеют только номера. Всего на линии $n$ станций, они пронумерованы числами от 1 до $n$ по кругу, и за станцией номер $n$ идёт станция номер 1.

Новая линия проходит мимо дома Тани и её школы. Таня живёт на станции номер $a$ , а школа находится на станции номер $b$ . Определите, сколько времени понадобится Тане на дорогу на метро, если между двумя соседними станциями поезд движется 1 минуту (временем стоянки поезда следует пренебречь). На поезде можно передвигаться в любом из двух направлений кольцевой линии.

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

Первая строка входных данных содержит число $n$ — количество станций на линии ( $2 \leq n \leq 1 0^{9}$ ). Вторая строка содержит номер станции $a$ , где живёт Таня ( $1 \leq a \leq n$ ). Третья строка содержит номер станции $b$ , где находится школа ( $1 \leq b \leq n$ ).

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

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

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

Решения, правильно работающие, когда $n \leq 100$ , будут оцениваться в 60 баллов.

Замечание

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

стандартный ввод	стандартный вывод
10 7 5	2

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

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

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

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

Расстояние между станциями с номерами $a$ и $b$ равно $∣ a - b ∣$ , если не проезжать участок от станции $n$ до станции 1. Если же поехать в другом направлении, то расстояние будет равно $n - ∣ a - b ∣$ . Из этих двух значений нужно выбрать наименьшее.

solution.py

n = int(input())
a = int(input())
b = int(input())
d = abs(a - b)
print(min(d, n - d))

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

solution.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, a, b;
    cin >> n >> a >> b;
    long long distance = llabs(a - b);
    cout << min(distance, n - distance) << "\n";
    return 0;
}

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

0.5 секунд, 256 мегабайт, математика, бинарный поиск

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

Для развития туризма решено открыть два прогулочных речных маршрута. Маршруты будут начинаться на одной из промежуточных пристаней (пристани номер 1 или $n$ не могут быть начальными точками маршрутов), один маршрут будет идти вверх по течению реки к пристани номер 1, другой маршрут будет идти вниз по течению к пристани номер $n$ . Промежуточных остановок на маршрутах нет.

Для подъёма вверх по течению реки судно тратит $a$ минут на один километр, а для спуска вниз по течению реки — $b$ минут на один километр. Определите, на какой пристани должны начинаться оба маршрута, чтобы их продолжительности различались как можно меньше. Это значит, что необходимо минимизировать модуль разности времени в пути двух маршрутов.

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

Первая строка входных данных содержит целое число $n$ ( $3 \leq n \leq 2 \cdot 1 0^{9}$ ) — общее количество пристаней на маршруте. Вторая строка содержит число $a$ — время подъёма судна на один километр вверх по течению реки, третья строка содержит число $b$ — время спуска на один километр вниз по течению, $1 \leq b < a \leq 2 \cdot 1 0^{9}$ .

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

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

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

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

Замечание

В примере из условия начальным пунктом маршрутов нужно сделать пристань 3. Тогда вверх по течению судно поднимется за $(3 - 1) \times 7 = 14$ минут, а вниз по течению реки спустится за $(8 - 3) \times 3 = 15$ минут. Разница в продолжительности маршрутов составит 1, меньшей разности в данном примере достичь невозможно.

стандартный ввод	стандартный вывод
8 7 3	3

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

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

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

Набрать 60 баллов можно при помощи перебора по ответу. Переберём все пристани с номерами от 2 до $n - 1$ , и для каждой из них посчитаем разность между продолжительностью пути вверх и вниз.

Пусть рассматриваемая пристань имеет номер $x$ , тогда продолжительность пути до пристани 1 равна $a (x - 1)$ , а вниз — $b (n - x)$ . Нужно найти такую пристань $x$ , для которой модуль разности этих величин будет наименьшим.

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

solution.py

n = int(input())
a = int(input())
b = int(input())

def ans(x):
    return abs((x - 1) * a - (n - x) * b)

d = 2
for i in range(3, n):
    if ans(i) < ans(d):
        d = i

print(d)

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

x = \frac{bn + a}{a + b} .

Это число было бы ответом, если задача решалась в действительных числах, когда началом маршрутов может быть любая точка. Но мы рассматриваем только целочисленные значения ответа, поэтому ответом может быть одно из двух целых чисел: указанное значение $x$ , округлённое вниз и вверх. Выберем из этих значений такое, для которого модуль разности времени пути до верхней и нижней пристани будет наименьшим, учтя, что ответ не может равняться 1 и $n$ . Такое решение имеет сложность $O (1)$ .

solution.py

n = int(input())
a = int(input())
b = int(input())
def ans(pos):
    return abs((pos - 1) * a - (n - pos) * b)
d = max(2, (b * n + a) // (a + b))
if d + 1 < n and ans(d + 1) < ans(d):
    d += 1
print(d)

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

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

solution.cpp

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

long long n, upTime, downTime;

long long difference(long long pier) {
    return llabs((pier - 1) * upTime - (n - pier) * downTime);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> upTime >> downTime;
    long long best = max(2LL, (downTime * n + upTime) / (upTime + downTime));
    best = min(best, n - 1);
    if (best + 1 < n && difference(best + 1) < difference(best)) {
        best++;
    }
    cout << best << "\n";
    return 0;
}

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

1 секунда, 256 мегабайт, жадный алгоритм

Рядом с Очень большой кольцевой линией построили новую дорогу, вдоль которой необходимо сделать благоустройство и посадить деревья. Городские службы определили места, в которых возможно посадить деревья, но биологи говорят, что расстояние между деревьями должно быть не менее чем $d$ метров. Определите, где нужно посадить деревья, чтобы расстояние между деревьями было не менее $d$ метров, а число посаженных деревьев было максимальным.

Введём на улице координатную прямую с единицей, равной 1 метру. Тогда возможная позиция для $i$ -го дерева имеет координату $x_{i}$ , а расстояние между двумя деревьями с координатами $x_{i}$ и $x_{j}$ равно $∣ x_{i} - x_{j} ∣$ .

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

В первой строке входных данных записано число $d$ — минимальное допустимое расстояние между деревьями, $1 \leq d \leq 1 0^{9}$ . Во второй строке записано количество возможных мест посадки деревьев $n$ , $1 \leq n \leq 1 0^{5}$ . Следующие $n$ строк содержат $n$ различных чисел $x_{i}$ ( $1 \leq x_{i} \leq 1 0^{9}$ ) — возможные координаты деревьев в порядке возрастания.

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

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

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

Решения, правильно работающие, когда $n \leq 10$ , $d \leq 10$ и все $x_{i} \leq 10$ , будут оцениваться в 20 баллов.

Решения, правильно работающие, когда $n \leq 100$ , $d \leq 100$ и все $x_{i} \leq 100$ , будут оцениваться в 40 баллов.

Решения, правильно работающие, когда $n \leq 100$ без дополнительных ограничений на $d$ и $x_{i}$ , будут оцениваться в 60 баллов.

стандартный ввод	стандартный вывод
3 5 2 3 6 9 10	3 6 10

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

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

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

Задача решается при помощи «жадного алгоритма». Пусть $x$ — координата очередной точки, в которую можно посадить дерево, а предыдущее дерево было посажено в точке с координатой prev. Тогда если x - prev >= d, то посадим дерево в точку $x$ , обновив значение prev = x.

solution.py

d = int(input())
n = int(input())
prev = -d
for i in range(n):
    x = int(input())
    if x - prev >= d:
        print(x)
        prev = x

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

solution.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long d;
    int n;
    cin >> d >> n;
    long long previous = -d;
    string output;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        if (x - previous >= d) {
            output += to_string(x);
            output += '\n';
            previous = x;
        }
    }
    cout << output;
    return 0;
}

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

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

Другие туры

2026/27

2025/26

2024/25

2023/24

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

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

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

или

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

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

Муниципальный этап ВсОШ по информатике 2024/25, 7–8 классы. ВсОШ 2024/25

Задачи тура

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

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

2. Треугольники

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

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

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

4. 90 минут

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

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

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

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

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

Замечание

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

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

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

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

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

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

Замечание

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

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

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

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

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

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

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

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

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

Другие туры

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

Муниципальный этап ВсОШ по информатике 2024/25, 7–8 классы.