Школьный этап, 9–11 классы всероссийской олимпиады по информатике: 5 задач с официальным разбором, к каждой наше решение на C++.

Школьный этап ВсОШ по информатике 2025/26, 9–11 классы.

Сириус, первая группа регионов, 21 октября 2025Условия PDF Разбор PDF Архив с тестами Сдать на Codeforces

Задачи тура

1Рекламные паузыматематика, целочисленное деление
2Популярный постматематика, жадный алгоритм
3Встреча у фонтанатеория чисел, НОД
4Раскраска стеныконструктив, раскраска
5Проблемы логистикижадный алгоритм, сортировка

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

1. Рекламные паузы

0.5 секунд, математика, целочисленное деление

Слон Семён включил в онлайн-кинотеатре новый фильм «Матрица». После каждых $a$ минут показа фильма вставляется реклама длиной $b$ минут. Но если в момент планируемого начала рекламного блока фильм завершается, то рекламу не показывают.

Фильм без рекламы длится $n$ минут. Сколько времени займёт показ всего фильма вместе с рекламой?

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

Первая строка входных данных содержит одно целое число $a$ ( $1 ⩽ a ⩽ 1 0^{9}$ ) — длительность блока фильма между рекламами.

Вторая строка содержит одно целое число $b$ ( $1 ⩽ b ⩽ 1 0^{9}$ ) — длительность одного рекламного блока.

Третья строка содержит одно целое число $n$ ( $1 ⩽ n ⩽ 1 0^{9}$ ) — длительность оригинала фильма без рекламы.

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

Выведите одно целое число — длительность фильма с рекламой.

Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

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

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

Замечание

В первом примере будут показаны 4 рекламных блока через 20, 40, 60, 80 минут показа фильма.

Во втором примере будут показаны 3 рекламных блока через 30, 60, 90 минут показа фильма.

стандартный ввод	стандартный вывод
20 5 90	110

стандартный ввод	стандартный вывод
30 4 120	132

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

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

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

К длине фильма нужно добавить количество рекламных пауз, умноженное на продолжительность одной паузы $b$ . Рекламные паузы вставляются через каждые $a$ минут, поэтому для подсчёта их числа нужно поделить $n$ нацело на $a$ . Но если $n$ делится на $a$ (остаток от деления $n$ на $a$ равен 0), то время показа последней рекламной паузы совпадёт с окончанием фильма, поэтому реклама показываться не будет и число рекламных пауз нужно уменьшить на 1. Возможное решение.

solution.py

a = int(input())
b = int(input())
n = int(input())
n_pauses = n // a
if n % a == 0:
    n_pauses -= 1
print(n + n_pauses * b)

Можно написать решение и без использования if.

solution.py

a = int(input())
b = int(input())
n = int(input())
n_pauses = (n - 1) // a
print(n + n_pauses * b)

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

solution.cpp

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

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

2. Популярный пост

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

В новом мессенджере «Дружба» разработчики предусмотрели возможность оставить реакцию под сообщением. Каждый пользователь может оставить даже две разные реакции, но больше двух реакций выбрать нельзя. Под некоторым сообщением пользователи оставили $a$ реакций «Согласен», $b$ реакций «Не согласен» и $c$ реакций «Забавно». Какое минимальное количество пользователей могло отреагировать на данное сообщение?

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

В первой строке входных данных записано число $a$ , во второй $b$ , в третьей — $c$ из условия задачи ( $0 ⩽ a, b, c ⩽ 7 \cdot 1 0^{8}$ ).

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

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

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

Решения, правильно работающие, когда числа $a, b, c$ не превосходят 10, будут оцениваться в 45 баллов.

Замечание

В примере из условия два пользователя могли поставить реакции первого и третьего типов, третий пользователь поставил реакцию второго и третьего типов, а четвёртый пользователь — только реакцию третьего типа.

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

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

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

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

Если какое-то из чисел $a, b, c$ больше суммы двух других, то это число и является ответом: меньшее количество пользователей не могло оставить столько реакций, а если каждый пользователь поставил самую популярную реакцию из трёх и какую-то из двух оставшихся (или поставил одну самую популярную реакцию), то этот вариант будет реализован. Поэтому можно просто вывести наибольшее из трёх чисел.

solution.py

a = int(input())
b = int(input())
c = int(input())
print(max(a, b, c))

Такое решение набирает 50 баллов.

Рассмотрим теперь случай, когда максимальное из трёх чисел меньше суммы двух других. Необходимо наименьшему количеству пользователей назначить по две или одной реакции, чтобы общее число реакций трёх видов было равно $a, b, c$ . Реализуем «жадный» алгоритм — назначим очередному пользователю две различные реакции, уменьшив на 1 счётчики их количеств. Чтобы последующим пользователям также оставалась возможность выбрать две реакции, необходимо избежать ситуации, когда только одно из чисел $a, b, c$ является ненулевым. то есть выбирать на каждом шаге два наибольших значения из $a, b, c$ .

Приведём пример такого решения: входные числа упорядочиваются так, чтобы выполнялось условие $a ⩽ b ⩽ c$ , затем в цикле наибольшие значения $c$ и $b$ уменьшаются на 1, а значение ответа увеличивается на 1, после чего числа опять переупорядочиваются.

solution.py

a = int(input())
b = int(input())
c = int(input())
ans = 0
a, b, c = sorted([a, b, c])
while c > 0:
    c -= 1
    b -= 1
    ans += 1
    a, b, c = sorted([a, b, c])
print(ans)

Такое решение набирает 50 баллов. Но если объединить эти два решения и выводить $max (a, b, c)$ в случае, когда одно из чисел не меньше суммы двух других, а иначе реализовать «жадный» алгоритм, то решение получит 75 баллов.

Теперь избавимся от цикла в «жадном» алгоритме. Поскольку пользователь не мог оставить более двух реакций, то для количества пользователей $k$ выполняется неравенство

k ⩾ ⌈ \frac{a + b + c}{2} ⌉,

где $⌈ x ⌉$ — значение $x$ , округлённое вверх до целого числа.

Наш жадный алгоритм и реализует такую формулу: на каждом шаге, кроме, возможно, последнего, будут уменьшаться два из трёх чисел $a, b, c$ .

Таким образом, решение задачи дают формулы: $k = max (a, b, c)$ если одно из чисел не меньше суммы двух других (то есть если $2 max (a, b, c) ⩾ a + b + c$ ) или $k = ⌈ \frac{a + b + c}{2} ⌉$ иначе. Это можно записать и при помощи одной формулы

k = max (a, b, c, ⌈ \frac{a + b + c}{2} ⌉) .

Деление с округлением вверх можно реализовать, например, на языке Python при помощи выражения (a+b+c+1) // 2.

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

solution.py

a = int(input())
b = int(input())
c = int(input())
print(max(a, b, c, (a+b+c+1) // 2))

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

solution.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long a, b, c;
    cin >> a >> b >> c;
    long long answer = max({a, b, c, (a + b + c + 1) / 2});
    cout << answer << "\n";
    return 0;
}

3. Встреча у фонтана

0.5 секунд, теория чисел, НОД

Маша и Паша живут на одной улице, и их дома разделены только парком, в котором друзья любят гулять. В центре парка есть красивый фонтан, у которого Маша и Паша хотят сегодня встретиться. Известно, что Маша идёт до фонтана $m$ минут, Паша — $p$ минут.

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

Помогите друзьям понять, смогут ли они встретиться в парке у фонтана, и если да, то сколько минут пройдёт с момента выхода из домов до их встречи.

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

Первая строка содержит целое число $m$ ( $1 ⩽ m ⩽ 1 0^{9}$ ) — время в минутах, которое требуется Маше, чтобы дойти от дома до фонтана.

Вторая строка содержит целое число $p$ ( $1 ⩽ p ⩽ 1 0^{9}$ ) — время в минутах, которое требуется Паше, чтобы дойти от дома до фонтана.

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

Выведите одно целое число — время, через которое Маша и Паша смогут встретиться у фонтана, если выйдут из домов одновременно, или −1, если этого никогда не случится.

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

Решения, правильно работающие, когда $m$ и $p$ не превосходят $1 0^{3}$ , будут оцениваться в 30 баллов.

Решения, правильно работающие, когда ответ не превосходит $1 0^{9}$ , будут оцениваться в 60 баллов.

Замечание

Далее все временные отметки даются относительно начала движения, т.е. выхода из дома.

В первом примере из условия Маша придёт к фонтану через 3 минуты, развернётся и пойдёт назад. Паша придёт к фонтану через 5 минут и отправится домой. Через 6 минут Маша доберётся до дома, вновь окажется у фонтана через 9 минут, опять не найдёт Пашу, развернётся и пойдёт домой. В следующий раз она будет у фонтана через 15 минут. Паша же дойдёт до дома через 10 минут и вернётся к фонтану через 15 минут, где он и встретится с Машей.

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

стандартный ввод	стандартный вывод
3 5	15

стандартный ввод	стандартный вывод
5 10	-1

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

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

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

Каждый из двух персонажей перед встречей пройдёт расстояние от своего дома до фонтана нечётное число раз. Условие задачи формализуем так: нужно найти такое минимальное $t$ , что $t = m x$ , $t = p y$ , где $x$ и $y$ — нечётные числа.

В неэффективном решении переберём возможные значения $t$ и найдём такое значение $t$ , что $t$ делится на $m$ и $p$ , и что частные от деления нечётные.

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

solution.py

m = int(input())
p = int(input())
t = 0
while not (t % m == 0 and t % p == 0 and t // m % 2 == 1 and t // p % 2 == 1):
    t += 1
print(t)

Такое решение набирает 20 баллов из первой группы тестов. Чтобы набрать 30 баллов нужно добавить дополнительную проверку — выводить число −1, если не удалось найти ответ, проверив значения $t$ до $1 0^{6}$ .

Улучшим это решение. Можно перебирать не все значения $t$ , а только значения, равные $m x$ для нечётного $x$ или, наоборот, $p y$ для нечётного $y$ . А лучше рассмотреть два случая, и если $m > p$ , то перебирать числа вида $m x$ , иначе перебирать значения вида $p y$ .

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

solution.py

m = int(input())
p = int(input())
if m > p:
    t = m
    while not (t % p == 0 and t // p % 2 == 1):
        t += 2 * m
else:
    t = p
    while not (t % m == 0 and t // m % 2 == 1):
        t += 2 * p
print(t)

Это решение набирает 50 баллов (или 60 баллов, если выводить −1, когда не удалось найти ответ).

Рассмотрим полное решение. В равенстве $m x = p y$ поделим обе части на общий делитель чисел $m$ и $p$ . Тогда если $d$ — наибольший общий делитель $m$ и $p$ , и $a = m / d$ , $b = p / d$ , то числа $a$ и $b$ — взаимно простые и $a x = b y$ .

Поскольку $x$ и $y$ — нечётные, то при одном чётном из чисел $a$ или $b$ (они не могут быть чётными одновременно) одна сторона равенства будет чётной, а другая — нечётной, то есть такое невозможно и нужно вывести −1. Иначе в силу взаимной простоты $a$ и $b$ необходимо взять $y = a$ и $x = b$ .

Алгоритм Евклида можно реализовать самостоятельно, заменяя большее число на его остаток от деления на меньшее, или использовать функцию gcd из модуля math в Python.

solution.py

m = int(input())
p = int(input())

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

d = gcd(m, p)
a = m // d
b = p // d
if a % 2 == 0 or b % 2 == 0:
    print(-1)
else:
    print(m * b)

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

solution.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long m, p;
    cin >> m >> p;
    long long d = gcd(m, p);
    long long a = m / d;
    long long b = p / d;
    if (a % 2 == 0 || b % 2 == 0) {
        cout << -1 << "\n";
    } else {
        cout << m * b << "\n";
    }
    return 0;
}

4. Раскраска стены

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

Длина кирпича в два раза больше его высоты, то есть его можно представить, как прямоугольник размером $1 \times 2$ клетки. Стена сложена из $n$ рядов кирпичей, каждый ряд состоит из $m$ клеток. В любом ряду последовательность кирпичей сдвинута на 1 клетку по сравнению с вышележащим и нижележащим. То есть в каждом ряду может быть не более $m /2$ целых кирпичей, а в концах каждого ряда могут находиться половинки кирпичей. При этом в самом нижнем ряду слева лежит целый кирпич. На картинке приведён пример стены для $n = 4$ и $m = 7$ .

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

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

В первой строке входных данных записано число $n$ ( $1 ⩽ n ⩽ 10$ ) — количество рядов кирпичей в стене. Во второй строке записано число $m$ ( $1 ⩽ m ⩽ 20$ ) — длина каждого ряда кирпичей в клетках.

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

Программа должна вывести $n$ строк, каждая из которых содержит ровно $m$ цифр от 1 до 9 — цвета, в которые покрашены клетки стены. Если две соседние клетки относятся к одному и тому же кирпичу, то они записываются одинаковыми цифрами, в противном случае — различными. Размещение кирпичей в вашей раскраске должно соответствовать условию задачи (на левом конце нижней строки находится целый кирпич). Используйте минимально возможное количество цветов (разрешены любые цифры от 1 до 9, но количество различных использованных цифр должно быть наименьшим возможным для данного размера стены).

Не допускаются пробелы и другие символы между цифрами, пробелы в началах и на концах строк, пустые строки в выводе программы.

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

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

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

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

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

Для покраски всегда достаточно трёх цветов. Рассмотрим достаточно большой фрагмент стены и попробуем покрасить его в три цвета.

Начнём с целого кирпича в левом нижнем углу. Если три кирпича попарно соприкасаются, то они будут покрашены в разные цвета.

Продолжим, покрасив в три цвета два нижних ряда кирпичей.

Остальные ряды будут повторением двух нижних рядов.

Видим, что в нижнем и всех нечётных рядах повторяется последовательность цифр 112233, а во втором и других чётных рядах — та же последовательность, но со сдвигом на 3 цифры. Решение будет таким: создадим строку, повторив последовательность 112233 несколько раз. Для построения нечётных (считая снизу) рядов кирпичей выведем первые $m$ символов этой строки, а в чётных рядах — $m$ символов, но пропустив 3 начальных символа последовательности.

Есть ещё один частный случай. При $n = 1$ для раскраски достаточно двух цветов, т.к. ряд кирпичей всего один. В этом случае нужно образовать строку повторением последовательности 1122. При $n = 1$ , $m = 2$ нужен только один цвет (т.к. кирпич всего один), но этот случай можно не рассматривать отдельно.

Пример правильного решения.

solution.py

n = int(input())
m = int(input())
if n > 1:
    s = "112233" * 4
else:
    s = "1122" * 5
for i in range(n, 0, -1):
    if i % 2 == 1:
        print(s[:m])
    else:
        print(s[3:3 + m])

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

solution.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    string pattern;
    if (n > 1) {
        for (int i = 0; i < 5; i++) pattern += "112233";
    } else {
        for (int i = 0; i < 6; i++) pattern += "1122";
    }
    for (int row = n; row >= 1; row--) {
        if (row % 2 == 1) {
            cout << pattern.substr(0, m) << "\n";
        } else {
            cout << pattern.substr(3, m) << "\n";
        }
    }
    return 0;
}

5. Проблемы логистики

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

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

Число участников заключительного этапа ВсОШ 3025 сильно увеличилось по сравнению с предыдущими годами, поэтому компьютеров необходимо много. Все они уже разложены по $n$ контейнерам, $i$ -й из которых весит $w_{i}$ килограммов. Задачу доставки этих контейнеров поручили транспортной компании, у которой (по счастливой случайности) есть ровно $n$ машин, причём стоимость провоза одного килограмма груза на $j$ -й из машин равна $p_{j}$ рублей. Таким образом, стоимость перевоза контейнера номер $i$ на машине номер $j$ равна $w_{i} \cdot p_{j}$ рублей. В одной машине можно перевозить только один контейнер!

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

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

В первой строке вводятся числа $n$ и $k$ ( $1 ⩽ n ⩽ 1 0^{5}$ , $1 ⩽ k ⩽ 1 0^{18}$ ) — количество контейнеров и машин, а также максимально возможная стоимость перевозки одного контейнера.

В следующей строке находятся $n$ чисел $w_{1}, w_{2}, \dots, w_{n}$ ( $1 ⩽ w_{i} ⩽ 1 0^{6}$ ) — массы контейнеров.

В следующей строке находятся $n$ чисел $p_{1}, p_{2}, \dots, p_{n}$ ( $1 ⩽ p_{j} ⩽ 1 0^{6}$ ) — стоимости перевозки одного килограмма груза на каждой из машин.

Обратите внимание на то, что число $k$ и значение ответа в этой задаче могут превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

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

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

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

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

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

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

Решения, правильно работающие, когда $w_{1} = w_{2} = \dots = w_{n}$ , будут оцениваться в 20 баллов.

Замечание

В первом примере из условия максимальная стоимость перевозки будет равна $10 \times 7 + 2 \times 50 + 3 \times 20 + 8 \times 5 + 4 \times 25 = 370$ .

Во втором примере из условия ограничение по стоимости перевозки одного контейнера равно 350. Поэтому контейнер массой 300 кг можно перевести только по цене 1 рубль за килограмм, а цена 3 рубля за килограмм допустима только для контейнера массой 100 кг. Тогда для контейнера массой 200 кг останется только машина со стоимостью перевозки 2 рубля за килограмм, и соблюсти условие ограничения стоимости перевозки каждого контейнера не получится.

стандартный ввод	стандартный вывод
5 100 10 2 3 8 4 20 7 50 5 25	370

стандартный ввод	стандартный вывод
3 350 200 100 300 3 1 2	-1

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

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

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

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

Для $n ⩽ 3$ допустимо перебрать все возможные перестановки непосредственно в тексте программы, и такое решение наберёт 20 баллов. Реализация алгоритма перебора всех перестановок или использование стандартной функции языка программирования (например, в Python это permutations из модуля itertools, в C++ — next_permutation из algorithms), может получить до 40 баллов. Пример такого решения.

solution.py

import itertools

n, k = map(int, input().split())
w = list(map(int, input().split()))
p = list(map(int, input().split()))

ans = -1
for p1 in itertools.permutations(p):
    s = 0
    for i in range(n):
        if w[i] * p1[i] > k:
            break
        s += w[i] * p1[i]
    else:
        ans = max(ans, s)
print(ans)

Чтобы получить полное решение, сделаем наблюдение. Пусть есть два контейнера массами $w_{1}$ и $w_{2}$ , при этом $w_{1} > w_{2}$ . Первый контейнер перевозят со стоимостью перевозки $p_{1}$ , а второй — $p_{2}$ . Если при этом $p_{1} < p_{2}$ , а $w_{1} p_{2} ⩽ k$ , то есть можно поменять контейнеры местами, соблюдая ограничение стоимости перевозки, то стоимость перевозки увеличится.

Действительно, в первом случае стоимость перевозки равна $w_{1} p_{1} + w_{2} p_{2}$ , во втором случае — $w_{1} p_{2} + w_{2} p_{1}$ . Докажем, что

w_{1} p_{1} + w_{2} p_{2} < w_{1} p_{2} + w_{2} p_{1} .

Это эквивалентно неравенству

(w_{1} - w_{2}) (p_{1} - p_{2}) < 0.

которое верно, т.к. $w_{1} - w_{2} > 0$ , $p_{1} - p_{2} < 0$ .

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

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

solution.py

n, k = map(int, input().split())
w = list(map(int, input().split()))
p = list(map(int, input().split()))

w.sort(reverse=True)
p.sort(reverse=True)

ans = 0
for wi in w:
    i = 0
    while i < len(p) and p[i] * wi > k:
        i += 1
    if i < len(p):
        ans += p[i] * wi
        p.pop(i)
    else:
        print(-1)
        break
else:
    print(ans)

В этом решении мы упорядочим по невозрастанию массы контейнеров и тарифы. Перебирая массы в порядке невозрастания, находим первый подходящий по ограничению тариф, он и является наибольшим подходящим. Если такой тариф нашёлся, добавляем к сумме p[i] * wi и удаляем из списка найденный тариф, иначе выводим −1.

Это решение сложностью $O (n^{2})$ , так как поиск каждого подходящего тарифа и удаление его из списка имеет сложность $O (n)$ , набирает 60 или чуть больше баллов.

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

Можно хранить все допустимые тарифы для рассматриваемого контейнера в отдельном списке, упорядоченном по неубыванию. Тогда новые допустимые тарифы будем добавлять в конец списка (также в порядке неубывания), а потом извлечём из этого списка последний элемент, удалив его при этом, — это и есть наибольший среди всех элементов списка. В программировании такая структура данных (где можно добавлять или удалять элементы в конце списка) называется стеком, но для реализации стека можно использовать обычный список в языке Python или vector в языке C++. Особенностью стека сложность $O (1)$ всех операций с ним.

Такое решение имеет сложность $O (n lo g n)$ ввиду использования сортировки. Сложность последующих операции с проходом по элементам и работой со стеком — $O (n)$ . Пример такого решения.

solution.py

n, k = map(int, input().split())
w = list(map(int, input().split()))
p = list(map(int, input().split()))

w.sort(reverse=True)
p.sort()

ans = 0
i = 0
possible = []
for wi in w:
    while i < len(p) and p[i] * wi <= k:
        possible.append(p[i])
        i += 1
    if len(possible) > 0:
        ans += possible[-1] * wi
        possible.pop()
    else:
        print(-1)
        break
else:
    print(ans)

В языке C++ возможна и другая реализация эффективного решения с использованием контейнера multiset (мультимножество). Этот контейнер позволяет хранить упорядоченный набор чисел, а также быстро находить наибольший элемент, который не превосходит данный. Используем его в решении: поместим все доступные тарифы в multiset и переберём контейнеры в порядке неубывания масс. Для каждого контейнера определим максимально допустимое значение тарифа, найдём в multiset наибольшее значение, не превосходящее данное, и удалим его.

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

solution.cpp

#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    long long n, k, ans, x, y;
    cin >> n >> k;
    vector<int> w;
    multiset<long long> p;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        w.push_back(x);
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        p.insert(x);
    }
    ans = 0;
    sort(w.rbegin(), w.rend());
    for (auto x : w)
    {
        auto it = p.upper_bound(k / x);
        if (it == p.begin())
        {
            cout << -1 << endl;
            return 0;
        }
        --it;
        ans += (*it) * x;
        p.erase(it);
    }
    cout << ans << endl;
}

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

1. «Ленивое удаление». Запишем все тарифы в неубывающий список и будем искать подходящий тариф двоичным поиском. Но вместо удаления тарифа из списка (что выполняется долго) пометим его как удалённый. Поэтому после нахождения максимального подходящего тарифа двоичным поиском, если он оказался удалённым, нужно найти наибольший неудалённый элемент слева от данного.

2. «Ссылочная реализация». Чтобы не просматривать все элементы списка, пропуская удалённые, для каждого элемента запишем значение prev[j] — какого-то элемента, который находится левее данного. Если элемент $j$ не был удалён, то prev[j] == j. Иначе все элементы между prev[j] и $j$ будут удалёнными, поэтому их не надо просматривать, и в поиске неудалённого элемента нужно просто переходить от $j$ к prev[j]. Правда, prev[j] также может оказаться удалённым, поэтому требуется переходить в цикле от элемента $j$ к элементу prev[j], пока не найдётся неудалённый элемент (j == prev[j]) или пока элементы не закончатся (в этом случае j == −1).

3. «Сжатие путей». В этой реализации поиск неудалённого элемента осуществляется долго, т.к. на самом деле при переходе вида j = prev[j] значение $j$ будет уменьшаться на 1. Чтобы ускорить поиск можно использовать технологию сжатия путей — если мы один раз прошли по пути и нашли для какого-то элемента первый неудалённый элемент, нужно обновить значение prev для начала этого пути, чтобы в дальнейшем не проходить по нему целиком. В примере программы ниже это делается присваиванием prev[j_found] = j − 1.

solution.py

import bisect
import sys
n, k = map(int, input().split())
w = list(map(int, input().split()))
p = list(map(int, input().split()))
prev = [i for i in range(n)]
w.sort(reverse=True)
p.sort()
ans = 0
for wi in w:
    j_found = bisect.bisect_right(p, k // wi) - 1
    j = j_found
    while j >= 0 and prev[j] != j:
        j = prev[j]
    if j == -1:
        print(-1)
        sys.exit(0)
    ans += wi * p[j]
    prev[j_found] = j - 1
print(ans)

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

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

solution.cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> weights(n), prices(n);
    for (auto &w : weights) cin >> w;
    for (auto &p : prices) cin >> p;
    sort(weights.rbegin(), weights.rend());
    sort(prices.begin(), prices.end());
    vector<long long> available;
    int next = 0;
    long long total = 0;
    for (long long w : weights) {
        while (next < n && prices[next] * w <= k) {
            available.push_back(prices[next]);
            next++;
        }
        if (available.empty()) {
            cout << -1 << "\n";
            return 0;
        }
        total += available.back() * w;
        available.pop_back();
    }
    cout << total << "\n";
    return 0;
}

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

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

Другие туры

2026/27

2025/26

2024/25

2023/24

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

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

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

или

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

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

Школьный этап ВсОШ по информатике 2025/26, 9–11 классы. ВсОШ 2025/26

Задачи тура

1. Рекламные паузы

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

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

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

Замечание

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

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

2. Популярный пост

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

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

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

Замечание

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

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

3. Встреча у фонтана

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

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

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

Замечание

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

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

4. Раскраска стены

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

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

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

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

5. Проблемы логистики

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

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

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

Замечание

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

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

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

Другие туры

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

Школьный этап ВсОШ по информатике 2025/26, 9–11 классы.