Алгоритмы и программирование · 2 балла

Массив: сортировка

Файл и сортировка

Обработать большой файл, отсортировать или отфильтровать данные и найти два значения.

Алгоритмы два целых числа

Что проверяет

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

Основание: проект спецификации и кодификатора КИМ 2027. Открыть документы

Теория

Что нужно знать

Задание 26 — это программа, которая обрабатывает большой файл: читает числа или строки, сортирует их, отбирает подходящие объекты и находит две характеристики. Ответ — два целых числа, и оба должны быть верны, иначе вместо двух баллов будет один. В 2027 году проверяется умение обрабатывать целочисленную информацию с использованием сортировки.

Минимум для задания 26

читать файл построчно и разбирать первую строку с параметрами
хранить данные в списке, кортеже, словаре или множестве
сортировать по одному и нескольким ключам
фильтровать данные и считать сумму, минимум, максимум и количество
выбирать максимальное количество предметов при ограничении
заменять один выбранный предмет на более выгодный
решать задачи на максимальную стоимость через динамику и рюкзак
обслуживать поток заявок K устройствами
обрабатывать интервалы и события сканирующей прямой
решать задачи покрытия отрезков жадным алгоритмом
группировать объекты по ключу и считать агрегаты внутри групп
вести накопительную сумму с порогом и резервными копиями
отбирать лучших по нескольким критериям с учётом равенства
оценивать сложность при N = 10^5–10^6
проверять порядок двух ответов и правило округления

Файл и формат ответа

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

Прочитайте первую строку отдельно: в ней могут быть N, K, S, M или сразу несколько параметров.
Строк может быть от нескольких сотен до миллиона: держите решение линейным или O(N log N).
Сначала выводится то число, которое в условии названо первым; перепутанный порядок — ноль баллов.
Если верно только одно число из двух, ставится 1 балл, поэтому проверяйте оба ответа.
Уточните единицы измерения второго ответа: минуты, килограммы, Кбайты, номер ряда.
В конце программа должна вывести ровно два числа, без пояснений и лишних строк.

n, limit = map(int, f.readline().split())print(first, second)

Чтение и хранение данных

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

with open('26.txt') as f: закрывает файл автоматически; на экзамене допустимо и open(...).readline().
n = int(f.readline()) — когда первая строка содержит одно число.
a = [int(x) for x in f] — когда дальше идёт по одному числу в строке.
data = [tuple(map(int, line.split())) for line in f] — когда полей несколько.
Для K устройств хватит массива длины K, для N объектов — длины N; не путайте эти размеры.
Словарь d[key] и множество экономят время, когда значения — номера, артикулы или идентификаторы.

data = [tuple(map(int, line.split())) for line in f]d[key] = d.get(key, 0) + 1

Сортировка и ключи

Сортировка — главная операция задания 26. Она позволяет за один проход выбирать самые лёгкие предметы, ставить рядом подходящие пары и находить разрывы в рядах. Ключ задаёт, по какому полю сортировать и как разрешать равенства.

a.sort() сортирует по возрастанию, a.sort(reverse=True) — по убыванию.
a.sort(key=lambda x: x[1]) сортирует по второму полю; key=lambda x: (x[0], -x[1]) — по двум правилам.
Кортежи сравниваются слева направо: (start, end) сначала по началу, затем по концу.
Для интервалов часто нужна сортировка по правому концу, для заявок — по времени начала.
Сортировка в Python устойчивая: при равных ключах сохраняется исходный порядок; это важно, если условие ссылается на порядок в файле.
sorted(...) возвращает новый список, list.sort() меняет существующий.

a.sort(key=lambda x: (-x[1], x[0]))a.sort(key=lambda x: x[1])

Фильтрация и агрегаты

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

[x for x in a if cond] оставляет подходящие элементы.
sum(a), min(a), max(a), len(a) — базовые агрегаты.
sum(1 for x in a if cond) считает количество подходящих элементов.
Среднее sum(a) / len(a) — дробное; сравнивать с ним лучше через умножение, чтобы не ловить ошибки округления.
Два лучших значения ищите одним проходом: обновляйте лучший и второй результат.
Не вызывайте sum(a) внутри цикла по a: это превращает линейный алгоритм в квадратичный.

sum(1 for x in a if x % 2 == 0)avg = sum(a) / len(a)

Жадный выбор предметов

Классическая схема задания 26: есть N предметов с весом или объёмом и ограничение S. Чтобы взять как можно больше предметов, берут самые лёгкие. Когда количество уже максимально, второе число получают заменой одного выбранного предмета на более выгодный.

Отсортируйте предметы по возрастанию и накапливайте сумму, пока она не превысит S.
В отсортированном массиве первый не влезший предмет означает, что все следующие тоже не влезут, — можно остановиться.
Чтобы максимизировать один предмет при том же количестве, освободите место, убрав последний выбранный предмет.
Подходящий кандидат x должен помещаться: x <= S - (total - last).
Жадность по весу не работает для «максимальной стоимости» с произвольными ценностями — там нужна динамика; в 26-м обычно максимизируют количество.
Проверьте, что один и тот же предмет не выбран дважды: кандидатов берите из ещё не выбранной части массива.

total + x <= Sx <= S - (total - last)

Два указателя и бинарный поиск

Если массив отсортирован, пары и тройки можно искать без полного перебора. Два указателя двигаются только вперёд, поэтому получается O(N) или O(N²) вместо O(N³). Для вопроса «сколько чисел меньше X» подходит bisect.

Для суммы пары: l = 0, r = n - 1; если сумма мала — l += 1, если велика — r -= 1.
Для треугольника стороны a <= b <= c достаточно проверить a + b > c.
Перебирая i и j, двигайте правую границу r, пока a[i] + a[j] > a[r]; все k от j + 1 до r - 1 дают треугольник.
Количество подходящих троек добавляется как r - j - 1.
Для каждой потребности ищите минимальный подходящий предмет через bisect_left.
Сложность перебора троек O(N²) допустима при N до нескольких тысяч, но не при 10^5.

a[i] + a[j] > a[r]bisect_left(a, x)

K устройств и заявки

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

free = [0] * K — время, когда исполнитель снова доступен.
Ищите первый по номеру свободный объект: if free[i] <= start или free[i] < start, если освобождение доступно только со следующей минуты.
Перерыв задаётся так: free[i] + rest <= start.
Если свободных нет, заявка отклоняется; считайте обслуженные и отклонённые отдельно.
Второй ответ — номер последнего использованного исполнителя, максимум прибыли или число отказов.
Для камер хранения с типами и объёмами сначала фильтруйте по типу и объёму, затем выбирайте минимальный объём и минимальный номер.
При больших K линейный поиск каждого исполнителя станет медленным — тогда нужна куча heapq.

free[i] <= startfree[i] + rest <= start

Интервалы и события

Задачи про одновременные события решаются сканирующей прямой. Начало интервала даёт +1, конец -1; после сортировки событий баланс показывает, сколько событий активно в каждой точке.

events.append((l, 1)) и events.append((r, -1)); сортируйте по времени.
Если отрезки [1; 5] и [5; 8] считаются пересекающимися, при равном времени сначала обрабатывайте начало, потом конец.
Если события в одной точке совместимы (конец одного и начало другого), порядок обратный: сначала конец.
Максимум активных — это максимальное значение баланса после обработки события.
Длину промежутка с максимумом считайте как сумму t - prev, пока баланс равен максимуму.
Количество пересекающихся пар: при обработке начала прибавьте текущий баланс — столько активных интервалов пересекается с новым.
Для вопроса «сколько событий шло одновременно» не нужно строить массив на 10^9 точек: хватит 2N событий.

bal += deltaans = max(ans, bal)

Покрытие отрезков

Задачи про камеры, ремонт дороги и подрядчиков — это покрытие отрезков. Минимальное число точек, покрывающих все интервалы, даёт жадность по правому концу. Если нужно покрыть заданный отрезок [A; B], сортируют по левому концу и на каждом шаге берут самый дальний правый конец.

Для минимального числа камер: сортировка по правому концу; камера ставится в правый конец первого непокрытого отрезка.
Следующий отрезок уже покрыт, если его левый конец не больше последней камеры.
Для покрытия [A; B]: среди отрезков с L <= A выбирайте максимальный R, затем переносите A в этот R.
Второй ответ «максимальное начало последнего участка» требует отдельной проверки кандидатов, заканчивающихся за B.
Для минимального расстояния между последними камерами рассматривают два жадных прохода: слева направо и справа налево.
Проверяйте, включены ли границы: L <= A и R >= B.

if L > last_camera: поставить камеру в RA = max_R

Группировка по ключу

Если объекты описываются парой «ключ — значение» (ряд и место, артикул и цена, клиент и объём), сначала соберите их в словарь. Затем обрабатывайте каждую группу отдельно: сортируйте, считайте сумму, ищите разрывы или максимум.

d.setdefault(key, []).append(value) собирает список по ключу.
collections.defaultdict(list) делает то же самое короче.
Для мест в ряду используйте множество: быстро проверять занятость и искать свободные подряд места.
Для артикулов храните количество, сумму и остаток; итог считайте после чтения всех строк.
Для пар «цвет + диаметр» ключом может быть кортеж (color, size).
При равных агрегатах уточните правило: больший или меньший номер, порядок в файле, минимальная цена.
Не сортируйте весь словарь, если нужен только максимум: достаточно пройти по значениям.

d.setdefault(row, set()).add(seat)d[(color, size)] = d.get((color, size), 0) + 1

Накопительная сумма и резервные копии

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

Храните текущий объём cur и список объёмов копий backups.
Перед добавлением проверяйте cur + volume > limit; если да — добавьте cur в копии и обнулите буфер.
После проверки добавляйте объём запроса: cur += volume.
Суммы по клиентам удобно копить в словаре client -> volume.
Ограничение по времени применяйте к сумме и к копиям отдельно: сравнивайте время как строку ЧЧ:ММ:СС или переводите в секунды.
Второй ответ — сумма двух последних или двух наибольших копий; читайте формулировку внимательно.
Если запрос сам больше буфера, уточните в условии, что считается копией; обычно такие данные не встречаются.

if cur + v > K: backups.append(cur); cur = 0cur += v

Сложность и проверка

При N = 10^5–10^6 сортировка O(N log N) работает за секунды, а двойной перебор O(N²) — нет. Отдельно следите за памятью: массив на 10^9 элементов не поместится, а словарь на N ключей — поместится.

O(N log N) — сортировка; O(N) — один проход, два указателя, события.
O(N²) допустим для N до 2–5 тысяч, но не для 10^5.
Не создавайте массивы размером с максимальную координату, если координаты до 10^9: используйте словарь или сжатие.
Проверьте пустой ввод, один элемент, равные значения и границы <= и <.
Сверьте ответ на маленьком примере из условия, если он есть.
Убедитесь, что выведены оба числа в нужном порядке и без лишнего текста.

N = 10^6: O(N log N) — норма, O(N^2) — нет

Разбор примера

Учебный пример: грузовик и максимальный груз

Грузоподъёмность грузовика 15. Массы грузов: 4, 6, 10, 7, 5, 5. Нужно увезти как можно больше грузов, а при максимальном количестве — взять самый тяжёлый груз. Покажем жадный выбор и замену последнего груза.

Выбор грузов при грузоподъёмности 15
Шаг	Масса	Сумма	Количество
1	4	4	1
2	5	9	2
3	5	14	3
4	6	20 > 15 — стоп	3
Замена	6 вместо 5	4 + 5 + 6 = 15	3

Отсортируем массы: 4, 5, 5, 6, 7, 10.
Берём самые лёгкие, пока сумма не превышает 15: 4 + 5 + 5 = 14, это 3 груза.
Следующий груз 6 не помещается: 14 + 6 > 15.
Проверяем замену последнего груза: свободно 15 - (14 - 5) = 6.
Груз 6 подходит, получаем 4 + 5 + 6 = 15 при том же количестве 3.
Максимальная масса в наборе равна 6.

Ответ3 6

Способы решения

Выберите метод под формулировку

Методы собраны по решениям задания 26 из базы Kompege. Начните с того, что именно нужно найти в условии.

максимум количества при ограничении

Жадный набор: побольше предметов, затем самый тяжёлый

Когда использовать: Нужно выбрать как можно больше предметов при ограничении на суммарный вес или объём, а вторым числом вернуть максимальный вес одного выбранного предмета.

Отсортируйте веса по возрастанию.
Накапливайте сумму и количество, пока очередной предмет помещается в ограничение.
Запомните последний выбранный предмет и общую сумму.
Освободите место, убрав последний предмет: free = limit - (total - last).
Среди ещё не выбранных найдите самый большой предмет не больше free и замените последний.
Выведите количество и максимальный вес после замены.

Если предметы уже отсортированы, первый не влезший предмет означает остановку: все следующие тяжелее.
Замена последнего предмета даёт максимально возможное освободившееся место, поэтому остальные варианты проверять не нужно.
Если нужно максимизировать не вес, а другой признак, замените формулу свободы места на свою.
При равных весах берите любой — на количество это не влияет.
Для «архива на диск» предметы — файлы, для «рюкзака» — банки, для «грузовика» — грузы.
Если количество получилось 0, аккуратно обработайте этот случай.

Пример

Грузоподъёмность 15, массы 4, 6, 10, 7, 5, 5. Найдите наибольшее количество грузов и максимальную массу груза в таком наборе.

f = open('26.txt')
n, limit = map(int, f.readline().split())
a = sorted(int(x) for x in f)

total = count = 0
for x in a:
    if total + x <= limit:
        total += x
        count += 1
    else:
        break

last = a[count - 1]
free = limit - (total - last)
best = last
for x in a[count:]:
    if last <= x <= free:
        best = max(best, x)

print(count, best)

ОтветСначала берём 4 + 5 + 5 = 14 (3 груза). Заменяем последнюю 5 на 6: 4 + 5 + 6 = 15, количество сохраняется. Ответ: 3 6.

По решениям № 24, 889, 14001, 16768.

каждый второй, каждый пятый, порядок выбирает покупатель

Скидки и порядок: какие позиции получают скидку

Когда использовать: Скидка зависит от позиции товара в чеке, а порядок товаров можно выбирать; нужно получить минимальную или максимальную сумму покупки.

Отсортируйте цены по возрастанию.
Определите, сколько позиций получают скидку: например, половина товаров или каждый второй.
Для минимальной суммы поставьте на скидочные позиции самые дорогие товары.
Для максимальной суммы — самые дешёвые.
Сложите полные цены и вычтите суммарную скидку; округление выполняйте по правилу задачи.

Если скидка даётся на каждый второй товар, скидочных позиций n // 2.
При нечётном числе товаров последний товар может остаться без пары — проверьте правило.
Если скидка только на товары дороже порога, сначала отфильтруйте подходящие, затем распределяйте.
Порядок внутри скидочных позиций не важен: важна только сумма их цен.
Округление вверх или вниз применяйте ко всей сумме или к каждой позиции — это указано в условии.
Для «каждая пятая пачка бесплатно» бесплатными выгодно делать самые дорогие пачки.

Пример

Цены 100, 200, 300, 400. Каждый второй товар получает скидку 50%, порядок выбирает покупатель. Найдите минимальную и максимальную сумму.

prices = sorted([100, 200, 300, 400])
k = len(prices) // 2
total = sum(prices)

pay_min = total - sum(prices[-k:]) / 2
pay_max = total - sum(prices[:k]) / 2

print(int(pay_min), int(pay_max))

ОтветМинимум: скидка на 400 и 300, сумма 650. Максимум: скидка на 100 и 200, сумма 850. Ответ: 650 850.

По решениям № 636, 16592, 20161.

треугольники, суммы, подбор пар

Пары и тройки: два указателя после сортировки

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

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

В треугольнике после сортировки достаточно проверить a + b > c: остальные неравенства выполняются автоматически.
Правая граница не должна откатываться назад: при росте j сумма a[i] + a[j] не убывает.
Если все числа различны, пара и тройка считаются по значениям; если нет — по элементам массива.
Для пар с суммой не больше S подходит классический two pointers.
Для поиска ближайшего числа используйте bisect_left и bisect_right.
Проверьте, нужно ли учитывать порядок элементов: обычно пары и тройки — неупорядоченные.

Пример

Даны числа 14, 10, 13, 13. Найдите количество троек, из которых можно составить треугольник, и максимальную сумму такой тройки.

f = open('26.txt')
n = int(f.readline())
a = sorted(int(x) for x in f)

count = best = 0
for i in range(n - 2):
    r = i + 2
    for j in range(i + 1, n - 1):
        while r < n and a[i] + a[j] > a[r]:
            r += 1
        count += r - j - 1
        if r - 1 > j:
            best = max(best, a[i] + a[j] + a[r - 1])

print(count, best)

ОтветПодходят (10, 13, 13), две тройки (10, 13, 14) и (13, 13, 14). Всего 4, максимальная сумма 40. Ответ: 4 40.

По решениям № 10072, 11921, 26624.

курьеры, такси, репетиторы, камеры хранения

K устройств: заявки, освобождение и отказы

Когда использовать: Заявки обслуживают K исполнителей, и важно, кто освободился раньше, сколько заявок принято и какое устройство использовалось последним.

Прочитайте K, N и все заявки.
Отсортируйте заявки по времени начала, при равенстве — по времени окончания.
Создайте массив free из K нулей — время освобождения каждого исполнителя.
Для каждой заявки найдите первый по номеру исполнитель с free[i] <= start.
Обновите free[i] = end, увеличьте счётчик и запомните номер.
Если свободных нет, заявка отклоняется.

Если исполнитель доступен только со следующей минуты, используйте free[i] < start.
Перерыв между заявками добавляйте к времени освобождения: free[i] + rest <= start.
Для камер хранения с типами и объёмами сначала проверьте тип и объём, затем минимум по объёму, затем по номеру.
Второй ответ может быть числом отказов, номером последнего исполнителя или максимумом прибыли — прочитайте формулировку.
При K до нескольких сотен линейный поиск нормален; при больших K используйте heapq.
Не путайте N заявок и K исполнителей при создании массивов.

Пример

K = 2, заявки: (0, 10), (5, 15), (12, 20). Найдите количество обслуженных заявок и номер исполнителя, обслужившего последнюю.

f = open('26.txt')
k = int(f.readline())
n = int(f.readline())
a = sorted(tuple(map(int, line.split())) for line in f)

free = [0] * k
served = last = 0

for start, end in a:
    for i in range(k):
        if free[i] <= start:
            free[i] = end
            served += 1
            last = i + 1
            break

print(served, last)

ОтветПервую заявку берёт исполнитель 1, вторую — 2, третью снова 1. Обслужено 3, последний — 1. Ответ: 3 1.

По решениям № 11243, 12909, 18028, 29234, 30401.

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

События и одновременность: максимум активных

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

Превратите каждый интервал в два события: начало +1, конец -1.
Отсортируйте события по времени; при равенстве сначала обрабатывайте начало, если касание считается пересечением.
Идите по событиям, поддерживая баланс активных интервалов.
Обновляйте максимум баланса.
Для длительности суммируйте промежутки, где баланс равен максимуму.

Для пар пересечений при начале добавляйте текущий баланс до увеличения.
Если интервалы не пересекаются в общей точке, при равном времени сначала обрабатывайте конец.
Не создавайте массив на всю координатную ось: событий всего 2N.
Для поиска максимальной длины непрерывного участка с максимумом храните предыдущее время.
Проверьте, входят ли концы интервалов в событие: от этого зависит порядок при равном времени.
Для вопроса «сколько человек было в магазине в момент t» баланс после события и есть ответ.

Пример

Интервалы [1; 4], [2; 6], [5; 8]. Найдите максимальное число одновременных событий и суммарную длину промежутков с этим максимумом.

f = open('26.txt')
n = int(f.readline())
events = []
for _ in range(n):
    l, r = map(int, f.readline().split())
    events.append((l, 1))
    events.append((r, -1))

events.sort(key=lambda e: (e[0], -e[1]))

bal = best = best_len = 0
prev = events[0][0]
for t, delta in events:
    if t > prev:
        if bal > best:
            best, best_len = bal, t - prev
        elif bal == best:
            best_len += t - prev
    bal += delta
    prev = t

print(best, best_len)

ОтветМаксимум 2 события. Это промежутки [2; 4] длиной 2 и [5; 6] длиной 1, суммарно 3. Ответ: 2 3.

По решениям № 9847, 14705, 30460.

накрыть все участки, минимальное число

Покрытие отрезков: камеры и подрядчики

Когда использовать: Нужно покрыть все заданные отрезки минимальным числом камер или покрыть отрезок [A; B] минимальным числом подрядчиков.

Для камер отсортируйте отрезки по правому концу.
Поставьте камеру в правый конец первого отрезка.
Пропускайте отрезки, у которых левый конец не больше последней камеры.
Для покрытия [A; B] сортируйте по левому концу и выбирайте максимальный правый конец среди доступных.
Сдвигайте A в этот правый конец и повторяйте.
Второй ответ ищите отдельно по правилу задачи.

При равных правых концах порядок не важен.
Границы включаются: L <= A и R >= B.
Для минимального расстояния между последними камерами нужны два прохода — слева направо и справа налево.
Если покрыть отрезок невозможно, задача обычно гарантирует обратное; на всякий случай предусмотрите вывод.
Не путайте число камер с координатой последней камеры.
Жадность по правому концу оптимальна для точек, покрывающих интервалы; для произвольных длин отрезков проверяйте условие.

Пример

Участки [1; 4], [2; 5], [5; 7]. Найдите минимальное число камер, чтобы на каждом участке была камера, и минимальное расстояние между двумя последними камерами.

f = open('26.txt')
n = int(f.readline())
seg = sorted((tuple(map(int, line.split())) for line in f),
             key=lambda x: x[1])

cameras = [seg[0][1]]
for l, r in seg[1:]:
    if l > cameras[-1]:
        cameras.append(r)

print(len(cameras), max(l for l, r in seg) - cameras[-2])

ОтветКамеры в точках 4 и 7: первая покрывает [1; 4] и [2; 5], вторая — [5; 7]. Минимальное расстояние 5 - 4 = 1. Ответ: 2 1.

По решениям № 30461, 30464.

словарь и группы

Группировка по ключу: ряды, места, артикулы

Когда использовать: Объекты естественно группируются по ключу: ряд и места, артикул и товары, клиент и запросы, цвет и размер.

Соберите данные в словарь: ключ — группа, значение — список, множество или счётчик.
Для каждой группы отсортируйте значения, если важен порядок.
Найдите нужный агрегат: сумму, количество, максимум или разрыв.
Сравните группы по правилу из условия.
При равенстве примените дополнительный критерий: больший номер, меньшая цена, порядок в файле.

d.setdefault(key, set()).add(value) удобно для занятых мест.
Свободные места ищите как set(range(1, K + 1)) - occupied.
Для подряд идущих мест проверяйте окно длины need.
Для артикулов храните цену, остаток и количество продаж; выручка = цена × продано.
Если ключ составной, используйте кортеж: (color, diameter).
Не забывайте, что места и ряды могут нумероваться с 0 или с 1.
Сортировка групп нужна только там, где условие требует порядка.

Пример

В зале 3 ряда по 5 мест. Заняты места: ряд 1 — 1, 4; ряд 2 — 1, 2, 3; ряд 3 — 2. Найдите ряд с наибольшим номером, где есть 3 подряд свободных места, и первое место этой группы.

f = open('26.txt')
n, rows, seats = map(int, f.readline().split())
occupied = {}
for _ in range(n):
    row, seat = map(int, f.readline().split())
    occupied.setdefault(row, set()).add(seat)

need = 3
for row in sorted(occupied, reverse=True):
    free = set(range(1, seats + 1)) - occupied[row]
    for start in range(1, seats - need + 2):
        if all(x in free for x in range(start, start + need)):
            print(row, start)
            raise SystemExit

ОтветВ ряду 3 свободны места 1, 3, 4, 5; подходят 3, 4, 5. Ответ: 3 3.

По решениям № 16271, 21586, 31040, 17643, 22508.

порог, сброс, бэкапы

Накопительная сумма: сервер и резервные копии

Когда использовать: Запросы наполняют буфер ограниченного объёма; при переполнении создаётся резервная копия, а буфер очищается.

Прочитайте N, объём буфера и журнал запросов.
Заведите cur — текущий объём и backups — список копий.
Для каждого запроса проверьте, помещается ли он: cur + volume <= limit.
Если не помещается, добавьте cur в копии и обнулите буфер.
Добавьте объём запроса и обновите суммы по клиентам.
После чтения выберите нужные копии и клиента с максимумом.

Если условие говорит «копия перед добавлением», порядок именно такой: проверка, копия, добавление.
Суммы по клиентам копите в словаре; для ограничения по времени фильтруйте до накопления.
Время ЧЧ:ММ:СС сравнивается как строка, если формат фиксирован; иначе переведите в секунды.
Для «двух последних копий» берите backups[-1] и backups[-2], для «двух наибольших» — сортировку.
Проверьте, входит ли конечный момент 11:59:59 в ограничение.
Если буфер обнуляется после копии, не добавляйте старый объём повторно.
Для больших N храните только суммы по клиентам, а не весь журнал.

Пример

Буфер 10 Кбайт. Запросы: 09:00 клиент 1 — 4; 09:05 клиент 1 — 5; 09:10 клиент 2 — 3; 09:20 клиент 2 — 6; 09:30 клиент 1 — 4. Найдите клиента с наибольшим объёмом и сумму двух последних копий.

f = open('26.txt')
n, limit = map(int, f.readline().split())

cur = 0
backups = []
totals = {}

for line in f:
    t, client, volume = line.split()
    client, volume = int(client), int(volume)
    if t < '12:00:00':
        totals[client] = totals.get(client, 0) + volume
        if cur + volume > limit:
            backups.append(cur)
            cur = 0
        cur += volume

best = max(totals, key=totals.get)
print(best, backups[-1] + backups[-2])

ОтветКопии по 9 Кбайт создаются перед запросами 3 и 5; их сумма 18. Больше всех передал клиент 1 (13 Кбайт). Ответ: 1 18.

По решениям № 31131, 31137, 31232.

лучшие K, равенство баллов

Рейтинги и приоритеты: сортировка по нескольким ключам

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

Посчитайте основной показатель: сумму баллов, выручку, рейтинг.
Соберите кортеж с показателем и данными объекта.
Отсортируйте по убыванию показателя и возрастанию или убыванию дополнительного критерия.
Возьмите первые K элементов.
Выведите нужный номер и агрегат по первым K.

Ключ (-total, -extra, id) задаёт убывание двух показателей и возрастание номера.
Сортировка устойчивая: если ключ не различает элементы, сохраняется порядок файла.
Для «при равенстве выбрать меньший ID» добавляйте id последним полем ключа.
Если нужен только K-й элемент, всё равно часто проще отсортировать весь список.
Проверьте, считается ли K с нуля или с единицы.
Сумму первых K считайте после сортировки, а не во время чтения.

Пример

Студенты: (1, 80, 90, 70), (2, 70, 100, 70), (3, 60, 60, 60) — ID и три оценки. Нужны ID студента на 2-м месте и сумма баллов первых двух; при равенстве выше тот, у кого больше вторая оценка.

f = open('26.txt')
n, k = map(int, f.readline().split())
people = []
for line in f:
    ident, a, b, c = map(int, line.split())
    people.append((a + b + c, b, ident))

people.sort(key=lambda x: (-x[0], -x[1], x[2]))
print(people[k - 1][2], sum(x[0] for x in people[:k]))

ОтветУ студентов 1 и 2 по 240 баллов; выше второй из-за оценки 100. На 2-м месте ID 1, сумма первых двух 480. Ответ: 1 480.

По решениям № 17838, 20012, 23061, 2612.

агрегаты, среднее арифметическое, количество

Среднее и подсчёт по условию: один проход

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

Прочитайте все числа в список.
Посчитайте сумму и среднее.
Пройдите по списку и отберите элементы по условию.
Найдите количество и максимум или минимум среди отобранных.
Проверьте, строгие ли неравенства: больше или не меньше среднего.

Среднее может быть дробным; для сравнения используйте x * n > total, чтобы избежать плавающей точки.
Если нужен только максимум, не обязательно строить новый список.
Для «между средним и максимумом» проверьте оба неравенства.
Для товаров дороже средней цены учитывайте количество единиц, а не только число видов.
Если подходящих нет, max вызовет ошибку — обработайте пустой случай.
Среднее по всем единицам товара считается с весами: сумма цена × количество / сумма количеств.

Пример

Числа 10, 20, 30, 40. Найдите количество чисел, строго больших среднего, и максимальное из них.

f = open('26.txt')
n = int(f.readline())
a = [int(x) for x in f]

avg = sum(a) / n
bigger = [x for x in a if x > avg]

print(len(bigger), max(bigger))

ОтветСреднее 25; больше него 30 и 40. Ответ: 2 40.

По решениям № 107, 20012, 20426.

когда жадно нельзя

Динамика и рюкзак

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

Определите состояние: вместимость, позиция, номер предмета или пара координат.
Задайте dp[0] = 0, а недостижимые состояния — минус бесконечностью.
Для каждого предмета перебирайте вместимость в обратном порядке — так предмет не возьмётся дважды.
Для двумерной задачи используйте dp[x][y] или dp[i][w].
Восстановите ответ по dp или сохраните выбранные предметы.
Проверьте, что предмет не используется дважды и что ограничение не превышено.

0/1-рюкзак: цикл по вместимости назад; неограниченный рюкзак — вперёд.
Жадность по стоимости или удельному весу не всегда оптимальна: при разных ценностях нужна динамика.
Вложенные коробки: отсортируйте по размеру и считайте LIS или dp по совместимости.
Коробки разных цветов: добавьте в состояние цвет или проверяйте совместимость при переходе.
Путешествие по зонам: dp по зонам, где значение — минимальная стоимость или максимальный набор.
Занятость зала: сортируйте события и считайте dp по времени окончания.
Если веса большие, храните не массив, а словарь достижимых состояний.

Пример

Предметы (вес, стоимость): (2, 3), (3, 4), (4, 5). Вместимость 5. Найдите максимальную стоимость.

items = [(2, 3), (3, 4), (4, 5)]
W = 5
dp = [0] * (W + 1)
for w, v in items:
    for cap in range(W, w - 1, -1):
        dp[cap] = max(dp[cap], dp[cap - w] + v)
print(dp[W])

ОтветБерём предметы (2, 3) и (3, 4): стоимость 7. Ответ: 7.

По видео 2025 года, глава «Двумерная динамика (задача о рюкзаке)».

Шпаргалка: формулировка → метод

В условии	Что делать
«вместить как можно больше предметов»	сортировка по возрастанию, брать пока сумма не превысит S
«максимум предметов и самый тяжёлый из них»	заменить последний выбранный на самый большой, который влезает
«каждый второй или пятый со скидкой»	сортировка по цене; на скидочные позиции ставить самые дорогие или самые дешёвые
«порядок товаров выбирает покупатель»	минимум — скидка на дорогие, максимум — на дешёвые
«сколько троек — стороны треугольника»	сортировка и два указателя, проверять a + b > c
«подобрать пару или тройку по сумме»	сортировка и два указателя или bisect
«K курьеров, такси или репетиторов»	массив времени освобождения, первый свободный исполнитель
«камера хранения с типами и объёмами»	фильтр по типу и объёму, затем минимум по объёму и номеру
«максимум одновременно»	события +1 и -1, баланс активных
«сколько пар интервалов пересекается»	при старте прибавить текущий баланс
«накрыть все отрезки камерами»	сортировка по правому концу, камера в правый конец
«покрыть [A; B] подрядчиками»	сортировка по левому концу, жадно до максимального R
«ряд с местами»	группировка по ряду, множество занятых и поиск окон
«товары по артикулам или клиенты»	словарь счётчиков, затем агрегат по группе
«больше среднего, между средним и максимумом»	посчитать сумму и среднее, затем фильтр и агрегат
«сервер и резервные копии»	накопительная сумма; при переполнении копия и сброс
«максимальная стоимость при ограничении веса»	рюкзак: dp по вместимости, перебор назад
«вложенные коробки»	сортировка по размеру и динамика/LIS
«выбрать зоны путешествия»	динамика по зонам с минимальной стоимостью
«два ответа»	проверить порядок, равенство и правило округления

Видеоразборы по теме

Видеоразборы открытого курса КомпЕГЭ; для заданий 8–12 и 27 — дополнительные разборы демоверсии 2027.

По базе Kompege: 921 задача по заданию 26, 58 решений (52 программных и 6 текстовых) и 229 видеоразборов (159 YouTube, 37 VK, 33 Rutube). Для методов отобраны решения задач № 24, 107, 636, 889, 7602, 9756, 9847, 10072, 11243, 11921, 12909, 14001, 14705, 16271, 16592, 16768, 17838, 18028, 20012, 20426, 23061, 29234, 30401, 30460, 30461, 30464, 31040, 31131, 31137 и 31232; примеры переработаны в учебные.

Разборы из видео

Задачи, которые разбирают в курсе

Условия и код показаны в кадре в конце соответствующего фрагмента. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие.

№ 8102

разбор из видео · 2025

Конференц-зал: максимальная занятость и аренда

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

f = open('files/26-160.txt')
N = int(f.readline())
a = []
for s in f:
    st, end, p = [int(x) for x in s.split()]
    a.append([st, end, p])
a.sort(key=lambda x: x[1])

max_dlit = [(0, 0)] * N
for i in range(N):
    pred = [max_dlit[j] for j in range(i) if a[i][0] > a[j][1]]
    if pred:
        s, p = max(pred)
        max_dlit[i] = (s + (a[i][1] - a[i][0] + 1), p + a[i][2])
    else:
        max_dlit[i] = (a[i][1] - a[i][0] + 1, a[i][2])
print(max(max_dlit))

Ответ1432 619

Смотреть с 1:23:00

Полный архив

Все фрагменты видеоразборов

По одному пункту на каждую главу: условие или код из кадра, ответ и ссылка. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие; номер берётся из кадра. Текст с экрана распознан автоматически, служебные строки и артефакты удалены; если текст нечитаем, остаются название, таймкод и ссылка.

Показать все фрагменты (57)

2024 · 00:00 Приветствие

316) (Досрочный ЕГЭ-2023) Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке ¢ зшнимальным номером. Ячейки пронумерованы начиная с единицы. Размешение багажа в ячейке или её освобождение происходит в течение 1 Багаж можно поместить в только что освобожлённую ячейку начиная со следующей минуты. Если в момент слачи багажа свободных ячеек НЕТ, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 часов и какой номер будет иметь ячейка, которую займут последней.

Смотреть с 00:00

2024 · 05:40 Упорядоченная выборка 1

Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный ИБаеер объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей. В первой строке входного файла 26. $ — размер ни 8 52 свободного места на диске (натуральное число, не превышающее 100 000) и NN количество ы находятся значения объёмов фа

Смотреть с 05:40

2024 · 20:05 Упорядоченная выборка 2

самых дорогих — к премиум сегменту. По заданной информации о цене каждого из смартфонов определите цену самого дешёвого смартфона премиум сегмента, а также целую часть средней цены телефона из бюджетного сегмента. Входные и выходные данные. В первой строке входного файла 26-К5. tart находятся три числа, записанные через пробел: М — общее количество приведённых далее цен на смартфоны (натуральное число, не превышающее 10 000), К — количество смартфонов в бюджетном сегменте, М- количество смартфонов в премиум сегменте. В следующих М строках находятся значения цен на смартфоны (все числа натуральные, не превышающие 30000), каждое в отдельной строке. Запишите в ответе два числа:

Смотреть с 20:05

2024 · 27:35 Упорядоченная выборка 3

— общая цена покупки со скидкой округляется вверх до целого числа рублей; — порядок товаров в списке определяет магазин и делает это так, чтобы общая сумма скидки была he Вам необходимо определить общую цену закупки с учётом скидки и цену самого дорогого товара, на который будет предоставлена скидка. Первая строка входного файла 26-31. tact содержит число № — общее количество купленных товаров. Каждая из следующих N строк содержит одно целое число — цену товара в рублях. В ответе запишите два целых числа: сначала общую цену покупки с учётом скидки, затем цену самого дорогого товара, на который предоставлена скидка. Пример входного файла fo © > reba ok В данном случае товары

Смотреть с 27:35

2024 · 45:00 Упорядоченная выборка 4

Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, ит.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеолисанным правилам. Входные данные представлены в файле 26-39. В первой строке грузовика в кг. Каждая из следующих N строк содержит одно целое число — массу груза в кг. ответе запишите два целых числа: сначала максимально возможное количество грузов, затем их Пример организации исходных данных во входном файле: В данном случае сначала нуж

Смотреть с 45:00

2024 · 54:55 Подпоследовательности 1

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 54:55

2024 · 1:15:00 Подпоследовательности 2

Вхолные данные представлены в файле 26-58.txt следующим образом. В первой строке входного файла находятся два числа: $ — размер бюджет магазина (натуральное число, He превышающее 100 000) п № - количество товаров на складе у поставшика (натуральное число, не превышающее 10000).

Смотреть с 1:15:00

2024 · 1:37:40 Задача про ростовщика

Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, Входные данные представлены в файле 26-59. В первой строке входного файла находится одно число: М количество занятых мест (натуральное число, не превышающее 10 000). В следующих № строках находятся пары чисел: ряд и место выкупленного билета, He превышающие 100 000. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом Пример входного файла: в данном примере есть след

Смотреть с 1:37:40

2024 · 1:54:00 Многоуровневая сортировка 1 232

Для некоторого предприятия требуется закупить большое количество различных электронных компонентов. На рынке имеется множество предложений по различным компонентам, каждый из которых имеет какую-то цену. Для закупки предприятие выделяет средства таким "образом, чтобы купить все возможные компоненты и при этом купить как можно больше каждого из них, но не потратить на каждый THN более, чем определённую сумму денег $. Нужно определить, сколько всего компонентов удастся купить при таких условиях и какая наименьшая общая сумма денег будет на это потрачена. В первой строке входного файла находится два числа через пробел: число М - количество компонентов на рынке (натуральное число, не превышающее

Смотреть с 1:54:00

2024 · 2:07:15 Многоуровневая сортировка 2 2362

Для некоторого предприятия требуется закупить большое количество различных электронных компонентов. На рынке имеется множество предложений по различным компонентам, каждый из которых имеет какую-то цену. Для закупки предприятие выделяет средства таким образом, чтобы купить все возможные компоненты и при этом купить как можно больше каждого из них, но не потратить на каждый тип более, чем определённую сумму денег $. Нужно определить, сколько всего компонентов удастся купить при таких условиях и какая наименьшая общая сумма денег будет на это потрачена. В первой строке входного файла находится два числа через пробел: число М - количество компонентов на рынке (натуральное число, не превышающее

Смотреть с 2:07:15

2024 · 2:19:20 Многоуровневая сортировка 3

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 2:19:20

2024 · 2:25:50 Многоуровневая сортировка 4

Если при этих условиях есть несколько способов занупки, нужно потратить как можно Определите, сколько будет закуплено товаров типа 2 и сколько денег останется, Входные данные представлены в файле 26-62 вже следующим образом. Первая строка входного файла содержит два целых числа: N— общее количество товаров и М — сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква С или 2), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом. Запишите в ответе два числа: сначала количество закупленных товаров типа Z, затем оставшуюся неиспользованной сумму денег.

Смотреть с 2:25:50

2024 · 2:36:40 Многоуровневая сортировка 5

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 2:36:40

2024 · 2:46:15 Окончание и напутствия

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 2:46:15

2024 · 00:00 Приветствие

Смотреть с 00:00

2024 · 00:55 Максимальная вложенность 1

Определите количество цилиндров, которое пужно использовать для создания такой пирамиды, и максимально возможный радиус основания цилиндра, который будет находиться на вершине такой пирамиды. Входные данные В первой строке входного файла находится число М — количество цилиндров (uarypamsuoe число, ne превышающее 10 000). В следующих № строках находятся значения длин радиусов имеющихся цилиндров (все числа натуральные, ше превышающие 10 000}, каждое — в отдельной строке. сначала количество цилиндров, которое необходимо использовать для строительства пирамиды максимальной высоты, затем максимально возможную длину радиуса цилиндра, который можно поместить зершину такой пирамиды. Типовой пример организации данных во входном файле 5 53 50 42 50 40 Пример входного файла приведён для пяти цилиндров и случая, когда минимальная допустимая разница между длинами радиусов двух последовательно идущ

Смотреть с 00:55

2024 · 12:00 Максимальная вложенность 2

В первой строке нходного файла ивходится число № — количество коробок красного цвета в магазине (натуральное число, ме превышающее 10 000) и через пробел число М — количество коробок синего цвета в магазине (натуральное число. xe превышающее 10 000), В следующих № строках находятся значения длин сторон. коробок красного цвета (все числа натуральные, не превышающие 10 000) и через знак табуляции значения длин сторон коробок синего цвета (все числа натуральные, не превышающие 10 000), каждая пара таких значений — в отдельной строке; в последних М-М строках второе число опускается, н числа, соответствующие длинам сторон коробок красного цвета, идут каждое в отдельной строке.

Смотреть с 12:00

2024 · 20:20 Максимальная вложенность 3

Определите наибольшее количество коробок, которое можио использовать для упаковки одного поларка, и максимально возможную длину стороны самой маленькой коробки, FAC будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку. B первой строке входного файла находятся число № — количество коробок в магазине (натуральное число, ие превышающее 10 000) и через пробел число М — количество декоративных замочков в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длии сторон коробок (все числа натуральные, не превышающие 10 000) и через знак табуляции значения, указанные как маркиро

Смотреть с 20:20

2024 · 27:20 Максимальная цепочка элементов 1

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 27:20

2024 · 39:20 Максимальная цепочка элементов 2

квадраты, описанные в файле под номерами 2, Зи 5. двух квадратов, наиболее удалённых от начала координат, составит 30, вели на плоскость помещены квадраты 2, 4 u 5.

Смотреть с 39:20

2024 · 54:45 Окончание и напутствие

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 54:45

2024 · 00:00 Приветствие

Смотреть с 00:00

2024 · 02:50 Отбор чисел 1

a = [int(x) for x in f]
for i in range(ten(a)):
if sum(b)-b[-1]+a[i]<=s:
for i in range(n):
for i in range(Len(a)):

Смотреть с 02:50

2024 · 30:15 Отбор чисел 2

Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, ит.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество Входные данные представлены о файле 26-39. В первой строке входного файла записаны два целых числа: N— общее количество грузов и М - грузоподъёмность грузовика в xr. Каждая из следующих N строк содержит одно целое число — массу груза в KT. ответе запишите два целых числа: сначала максимально возможное ноличество грузов, затем их Пример организации исходных данных во входном файле:

for i in range(n):
if 180<=a[4]<=200:
alil = 0
m =m - sum(b)
while sum(c)+a[0]<:
for i in range(ten(e)):
print(len(b+c), sum(b+c))

Смотреть с 30:15

2024 · 56:00 Отбор чисел 3

Алгоритм скрипта обрабатывает файлы в порядке убывания их размера. Если файл помещается на диск, то следующий по размеру файл стараются поместить на следующий диск. Если не помещается, то на следующий, и так по кругу. Если файл не поместился ни на один диск, то он откладывается в локальную папку. Укажите в ответе два числа: объем всех отложенных файлов и их количество. Входные данные представлены в файле 26-56. В первой строке входного файла записаны значения V (объём диска), К (количество дисков) и № (количество Притаких входных данных ответ будет 31 и4:

a = [int(x) for x in f]
b = [0]*k
trash = []
for i in range(n):
for j in range(k, k+K):
k = +1
print(sum(trash), len(trash))

Смотреть с 56:00

2024 · 1:07:05 Как научиться кодить 26?

Алоритм скрипга обрабатывает файлы в порядке убывания их размера. Если файл помещается на диск, то следующий no размеру файл стараются поместить на следующий диск. объем всех отложенных файлов иих количество. входные данные представлены в файле 26-56. В первой строке входного файла записаны значения V (объём диска), K (количество дисков} WIN (количество архивов). Каждая из следующих М строк содержит одно целое число размер очередного архива. Пример входного файла: pw таких входных данных ответ будет 31 и:

a = [int(x) for x in f]
b = [0]*K
trash = [] +
for i in range(n):
for j in range(k, k+K):
k = je
print(sum(trash), len(trash))

Смотреть с 1:07:05

2024 · 1:10:35 Быстрый поиск чисел

Кабанов) В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чисел с чётной суммой, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких nap. Входные данные представлены в файле 26-45. Первая строка "содержит целое число М — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 10°. В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее. В данном случае есть три подходящие пары: 8 и 14 (среднее арифметическое 11), 14 и 2 (среднее арифметическое 8), 11

a = [int(x) for x in f]
b = set(a)
ans = []
for i in range(n):
for j in range(i+1,n):
if sr in b:

Смотреть с 1:10:35

2024 · 1:21:15 Быстрое сравнение чисел

Для каждой пары различных чисел из набора вычисляется значение К- количество, чисел из набора, меньших среднего арифметического этой пары. Необходино определить количество пар чисел сненулевым значением К, кратным сто, атакже наибольшее К среди этих "Входные данные представлены в файле 26-47 tact следующим образом. Первая строка содержит целое число М - общее количество чисел в наборе. Каждая из следующих М строк содержит одно число, не превышающее 10°. Пример входного файла: В примере рассмотрим пары co значением К кратным трём. В данном случае есть 14 подходящих = Например, для поры (9, 17) значение К равно 6 (6 чисел из набора меньше среднего.

Смотреть с 1:21:15

2024 · 1:34:30 Бинарный поиск

Кабанов) В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа "различны. Для каждой пары различных чисел из набора вычисляется значение K— количество чисел из набора, меньших среднего арифметического этой пары. количество пар чисел с ненулевым значением К, кратным ста, а также наибольшее К среди этих. Входные данные представлены в файле 26-47. Первая строка содержит целое число М — общее количество чисел в наборе. Каждая из следующих М строк содержит одно число, не превышающее 10. В ответе запишите два целых числа: сначала количество пар, затем наибольшее значение К. Пример входного файла: В примере рассмотрим пары co

ans = []
for i in range(n):
for j in range(it1,n):
count = itt
print(Llen(ans), max(ans))
a = Cint(x) for x in
for j in range(ie1,n):
count = bisect_left(a,sr)

Смотреть с 1:34:30

2024 · 2:00:10 ТЕЛЕПОРТАЦИЯ

Каждая жалоба описывает начало и конец проблемного участка (примерное расстояние от начала автомагистрали в метрах. Так как жалобы писались независимо друг от друга разными людьми, некоторые описываемые участки "автомагистрали накладываются друг на друга. Министерство решило узнать, "сколько участков дороги не требуют ремонта и какова длина наибольшего из них. В первой строке входного файла находится число М - количество жалоб (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа.

Смотреть с 2:00:10

2024 · 2:01:00 Хронология 1

foal. = [0]*2_000_001
if k i
count+=1
mx = max(mx, end-st)
print(count, mx)

Смотреть с 2:01:00

2024 · 2:13:27 Хронология 2

road = [0]*150_000
for i in range(n):
lamp = int(f.readline())
count = 0
for i in range(150000):
k+=road[i]
if count==500:
print(st, end-st)

Смотреть с 2:13:27

2024 · 2:27:25 Хронология 3

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 2:27:25

2024 · 2:41:15 Хронология 4

END = k+d
a = [0]*(d+1)
for i in range(n):
if (st<END or st==@) and (end>ST or end==0):
count = 0
for i in range(d+1):
print(mx, count)

Смотреть с 2:41:15

2024 · 3:01:45 Самый частый элемент

a[k1]+=1 an ee
a[k3]+=1
for i in range(10000):
if a[i]>m:
number = i
print(number, m)

Смотреть с 3:01:45

2024 · 3:07:50 Все возможные веса (HARD)

а) Сколько существует способов набрать ими вес М? 6) Какой вес можно выдать наибольшим количеством 2) вок 294 ro been Фесал С

a = [int(x) for x in f]
weight = [0]*(sum(a)+1)
for i in range(n):
weight2 = weight.copy()
for j in range(len(weight)):
if weight[j]>0:
for i in range(len(weight)):
print(w, af)

Смотреть с 3:07:50

2024 · 3:21:30 Окончание и напутствия

а) Сколько существует способов набрать ими вес М? 6) Какой вес можно выдать наибольшим количеством 4) Терельс- Fa CRY eo gh, ина.

a = [int(x) for x in f]
weight = [0]*(sum(a)+1)
for i in range(n):
weight2 = weight.copy()
for j in range(len(weight)):
if weight[j]>0:
for i in range(len(weight)):
if weight[i]>m:
print(w, nf)

Смотреть с 3:21:30

2024 · 00:00 Приветствие

Смотреть с 00:00

2024 · 02:30 Организация очереди (досрок 2023)

(№ 6316) (Досрочный ЕГЭ-2023) Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время слачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с инимальным номером. Ячейки пронумерованы начиная с елинииы. Размешение багажа в ячейке или её освобождение происходит в течение 1 Багаж можно поместить в только что освобожаённую ячейку начиная со следующей минуты. Если в момент слачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 часов и какой номер будет иметь ячейка, которую займут последней.

for j in range(1, K+1):
if camera[j]<st:
camera[j] = end
count = 0
last = 0
for i in range(N):

Смотреть с 02:30

2024 · 18:50 Организация очереди (две парковки)

Если в один момент подошли несколько клиентов, то они становятся в очерель в порядке расположения анных в файле. Клиент, стояший первым в очереди, подходит к первому освоболившемуся банкомагу (если таких несколько — K банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в Ty же MINTY, огл банкомат станет свободным. Известно время в минутах OT начала суток, HOTA клшент полошёл K банкомату. Определите наибольшее количество клиентов. которые были обслужены одним банкоматом за 24 часа. п время начала обслуживания последнего клиента. Последним обслуженным клиентом считается тот, который подошёл к любому банкомату so оконч

Смотреть с 18:50

2024 · 35:40 Организация очереди (ожидание + ограничение времени)

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 35:40

2024 · 56:45 Организация очереди (задержка + ограничение времени)

Входные данные представлены в файле 26-122. Первая строка входного файла "содержит лва натуральных числа, записанных через пробел: К (1 К < 100) — количество ломиков в олной линии, и М (1 SN 5 106) - количество заявок. Каждая из N последующих строк описывает содержит два пелых числа: час заезда п час выезда, считая OT начала сезона. В ответе запишите два пелых числа: максимальный номер линии, в которой будет заселяться хотя бы один дом

Смотреть с 56:45

2024 · 1:20:20 Организация очереди (число необходимых ячеек + число занятых ячеек)

Каждая заявка солержит олно число — количество билетов. и при этом максимально близко к началу ряда. Определите, сколько заявок подтвердит оператор и сколько свободных мест останется ва сталлоне после распрелеления всех заявок по описанному алгоритму. "Brome данные презставлены в файле 26-1245 следующим образом.

Смотреть с 1:20:20

2024 · 1:36:10 Организация очереди (опустошение ячеек)

Вхолные данные представлены в файле 26-75.154 следующим образом. В первой строке входного файла нахолится число М — общее количество пассажиров (натуральное число, не превышающее 10 000). следующих N строках нахолится по два числа. Первое число — время входа пассажира от начала рейса (натуральное число, не превышающее 1 000 000). Второе число - время выхода пассажира от начала рейса (натуральное число, не превышающее 1 000 000). Запишите в ответе два числа: количество пассажиров, одновременно находящихся в автобусе п общее время, когда в автобусе был хотя бы один пассажир. Пример входного файла: В приведённом примере пассажиры были в временных отрезках 10-40 и 50-180.

Смотреть с 1:36:10

2024 · 1:46:00 Временная линия 1

находятся два числа через пробел: число L — общая длина рабочего дня (натуральное число, не превышающее 109) п число N — количество изготовленных деталей (натуральное число, не превышающее 10 000). следуюших N строках нахолится по два числа через пробел. Первое число — время начало обработки от начала "рабочего дня (натуральное число, не превышающее 109). Второе число — время окончания обработки (натуральное число, не превышающее 10°). Запишите в ответе два числа: суммарную длительность простоев за день п длительность наибольшего простоя. Притаких условиях имеется два простоя: Их суммарная лительность 350, наибольший имеет длину 200, Ответ:

Смотреть с 1:46:00

2024 · 2:00:35 Временная линия 2

находятся лва числа через пробел: число L — общая длина рабочего дня (натуральное число, He превышающее 109) ичисло N — количество изготовленных деталей (натуральное число, He превышающее 10 000). следуюших N строках нахолится по два числа через пробел. Первое число — время начало обработки от начала "рабочего дня (натуральное число, не превышающее 109). Второе число — время окончания обработки: (натуральное число, не превышающее 10°). суммарную длительность простоев за день и длительность наибольшего простоя.

day = [0]*(L+1)
for i in range(st, end+1):
day[i] = 1
if k>0:

Смотреть с 2:00:35

2024 · 2:06:15 СКИП СКИП СКИП

В первой строке входного файла находятся два числа через пробел: число L — общая длина рабочего дня (натуральное число, He превышающее 71/1711 7100000 0000 { 109) ичисло — количество изготовленных деталей (натуральное число. рабочего ня (натуральное число. Второе число — время окончания обработки (натуральное число, не превышающее 10°), Запишите в ответе лва числа: суммарную длительность простоев за день и длительность наибольшего простоя. Пример входного файла::

Смотреть с 2:06:15

2024 · 2:11:35 Решаю как положено

Вхолные данные представлены в файле 26-76.1st следующим образом. В первой строке входного файла находятся лва числа через пробел: число Г — общая длина рабочего дня (натуральное число, He превышающее 10°) nsmeno № — количество паготовленных деталей (иитуральюе число, не превышающее 10000). следуюших М строках нахолится по два числа через пробел. Первое число — время начало обработки OT начала "рабочего дня (натуральное число, не превышающее 10°). Второе число — время окончания обработки (натуральное число, не превышающее 10°). Запишите в ответе два числа: суммарную длительность простоев за день и длительность наибольшего простоя. Пример вхолного файл имеет длину 200.

day = [0]*(L+1)
for i in range(N):
day[st]+=1
t = max(m,c)
print(s, m) &

Смотреть с 2:11:35

2024 · 2:20:50 Рекомендации

"Водные данные презстивлены в файле 6110's} следую образом, Tepe строк ктолного файла

bus = 0
for J in range(Lem):

Смотреть с 2:20:50

2024 · 2:23:30 Окончание и напутствия

Noe количество автомобилей, приехавших ка MapROBKY в теченше суток 1.

auto = 0
for i in range(N)
if park[j]<=st:
park[j] = end
auto += 1
for j in range(L,L+M):
park = [o]*(i+4)
bus = 0
for 4 in range(u):
for J in range(L+m):

Смотреть с 2:23:30

2025 · 00:00 Задача про вложенные коробки

a = [int(x) for x in f]
max_zep = [0]*N
for i in range(N):
for j in range(i):
print(max(max_zep),max(a[i] for i in range(N) if max_zep[i]==1040))

Смотреть с 00:00

2025 · 13:20 Задача про вложенные коробки разных цветов

boxes = []
for s in f:
max_zep = [0]
for i in range(N):
print(mx,[boxes[i][0] for i in range(N) if max_zep[i]==mx])

Смотреть с 13:20

2025 · 37:55 Минимальная стоимость путешествия в зоны

(№ 8102) *Входной файл содержит сведения о заявках на проведение занятий в конферени- зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток), а также сумма, которую компания-организатор готова заплатить за аренду зала. Два мероприятия можно провести, если время окончания одного из них строго меньше времени начала другого. Определите максимальное время, в течение которого конферени-зал может быть занят, и общую сумму, которую в этом случае удастся получить зааренду. Гарантируется, что последовательность мероприятий, обеспечивающая максимальное время занятости, единственна. Входные данные представлены в файле 26-160.txt следующим образом.

Смотреть с 37:55

2025 · 1:01:50 Задача про максимальную занятость зала

(№ 8102) *Входной файл содержит сведения о заявках на проведение занятий в конферени- зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток), а также сумма, которую компания-организатор готова заплатить за аренду зала. Два мероприятия можно провести, если время окончания одного из них строго меньше времени начала другого. Определите максимальное время, в течение которого конферени-зал может быть занят, п общую сумму, которую в этом случае удастся получить за аренду. что последовательность мероприятий, обеспечивающая максимальное время занятости, единственна. входного файла записано натуральное число N (1 < № < 1000) — количество за

m = int(f.readLine())
if pred_dlit
print(mx)

Смотреть с 1:01:50

2025 · 1:23:00 Двумерная динамика (задача о рюкзаке)

(№ 8102) *Входной файл содержит сведения о заявках на проведение занятий в конферени- зале. В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток), а также сумма, которую компания-организатор готова заплатить за аренду зала. Два мероприятия можно провести, если время окончания одного из них строго меньше времени начала другого. Определите максимальное время, в течение которого конферени-зал может быть занят, и общую сумму, которую в этом случае удастся получить за аренду. Гарантируется, что последовательность мероприятий, обеспечивающая максимальное время занятости, единственна. входного файла записано натуральное число N (1 < № < 1000) — количество за

m = int(f.readline())
max_dlit = [(9,6)]*m
for i in range(n):
if pred_diit
print(mx)
gies = 22

Смотреть с 1:23:00

2025 · 1:55:10 ПРОГРЕВ

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:55:10

2025 · 2:00:15 Окончание и напутствия

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 2:00:15

Типичные ошибки

перепутан порядок двух ответов
не хватает памяти или времени
данные не отсортированы
неверный порядок при равенстве
границы интервалов: <= и < перепутаны
жадный выбор без проверки замены последнего предмета
K исполнителей путают с N заявок
одно число неверно — 1 балл

2 первичных балла; при одном верном числе из двух — 1 балл.

Практика

ФИПИОткрытый банк заданий Навигатор · 2026Алгоритмы ДемоверсияКИМ 2027 МетодикаРазбор ошибок 2026

Навигатор и методические рекомендации опубликованы в 2026 году: номера заданий в них могут отличаться от нумерации 2027 года. Ориентируйтесь на тему.