Как решать задание 26 ЕГЭ по информатике — сортировка и обработка данных
Разбор задания 26 ЕГЭ по информатике 2026: жадные алгоритмы, сортировка по нескольким ключам, обработка большого файла данных. Полный шаблон решения на Python с примерами.
Задание 26 — одно из двух «тяжёлых» заданий в конце КЕГЭ (вместе с заданием 27). Оно стоит 2 первичных балла — столько же, сколько задание 27, но сюжет здесь другой: не кластерный анализ, а сортировка, жадные алгоритмы и обработка больших объёмов данных. И если задание 27 многим кажется страшным из-за слова «кластеризация», то задание 26 на первый взгляд простое — но именно на нём теряют баллы те, кто не разобрался с деталями.
Разберём всё по порядку: что в задании 26, какие бывают формулировки, как выбирать критерий жадности, полный шаблон кода и типичные ошибки.
О задании 26 коротко
| Параметр | Значение |
|---|---|
| Номер | 26 из 27 |
| Баллов | 2 (оба числа ответа верны — 2, одно — 1) |
| Время | 30-40 минут рекомендуется |
| Входные данные | один файл, до 10 000-100 000 записей |
| Ответ | два числа |
| Тип | обработка массива данных |
| Ключевой навык | сортировка + жадный алгоритм |
На экзамене тебе дают текстовый файл с последовательностью записей. Типовая запись — это либо число, либо строка с несколькими полями (например, длительность, ценность). В первой строке файла — параметры задачи. Нужно вычислить по условию два числа — например, максимальную суммарную ценность и количество выбранных записей — и вписать оба в ответ.
Из-за объёма данных решение обязано быть эффективным: сортировка за O(n log n) плюс один проход. Квадратный алгоритм (перебор всех пар) на десятках тысяч записей будет считаться недопустимо долго, а полный перебор подмножеств не закончится никогда.
Типовые формулировки
Разберём 4 типа задач, которые покрывают почти все варианты задания 26. За ними стоит одна и та же идея: отсортируй по правильному ключу, пройди жадно, собери ответ. «Жадно» — значит на каждом шаге берём самый выгодный вариант и больше к этому выбору не возвращаемся.
Тип 1. «Успеть максимум дел»
Дано N задач, у каждой — длительность
tи ценностьv. У тебя есть общий бюджет времени T. Какой набор задач нужно взять, чтобы суммарная ценность была максимальной?
Это классическая задача о рюкзаке в «дробной» формулировке. Если задачи можно брать только целиком, то жадный алгоритм по убыванию плотности v/t на ЕГЭ почти всегда даёт оптимум: составители подбирают данные так, чтобы жадность работала.
Критерий сортировки: по убыванию v/t (ценность на единицу времени).
Тип 2. «Расписание без пересечений»
Даны N интервалов
(начало, конец). Нужно выбрать максимальное количество непересекающихся.
Классика, разбирается в первой главе любой книги по жадным алгоритмам. Критерий — сортировка по концу. Идём по отсортированному списку, берём первый интервал, потом каждый следующий, у которого начало ≥ конца последнего взятого.
Критерий сортировки: по возрастанию времени конца.
Тип 3. «K-й по порядку»
Найди N-й элемент, если отсортировать записи по такому-то критерию.
Тут даже жадность не нужна — просто правильная сортировка и выборка элемента по индексу. Коварство в том, что критерий обычно составной: например, «сортировать по убыванию суммы полей 2 и 3, при равной сумме — по возрастанию ID».
Критерий сортировки: составной, читай условие как инструкцию.
Тип 4. «Грузоподъёмность / рюкзак»
Есть N предметов с весом
wи ценностьюv. Грузовик везёт W кг. Максимальная суммарная ценность?
Это дискретный рюкзак. В общем случае он решается через динамическое программирование за O(n·W). Но в ЕГЭ-версии W обычно большое (10^6), зато составители подбирают веса так, что жадность по плотности даёт правильный ответ — либо задача формулируется так, что любой предмет можно взять частично.
Критерий сортировки: по убыванию v/w.
Главный приём — сортировка по нескольким ключам
В Python это делается одной строкой. Ключ передаётся в функцию sorted() через key=, и если ключей несколько — возвращаешь кортеж:
# Сортировка по убыванию ценности, при равной ценности — по возрастанию ID
data.sort(key=lambda x: (-x['value'], x['id']))
# Сортировка по убыванию плотности, при равной — по номеру
data.sort(key=lambda x: (-x['value'] / x['time'], x['id']))
# Сортировка по времени конца (классика задач на расписания)
intervals.sort(key=lambda x: x['end'])
Знак минус в -x['value'] инвертирует сортировку для этого поля — при этом остальные поля сортируются в обычном порядке. Это удобнее, чем писать reverse=True (который инвертирует все поля).
Почему не reverse=True
# ПЛОХО — инвертирует и value, и id
sorted(data, key=lambda x: (x['value'], x['id']), reverse=True)
# ХОРОШО — инвертирует только value, id сортируется по возрастанию
sorted(data, key=lambda x: (-x['value'], x['id']))
На экзамене это критично: при одинаковой ценности типовое условие требует меньший ID, и reverse=True даст неправильный ответ.
Полный шаблон решения на Python
Это универсальный скелет — под любой тип задания 26 в нём меняются только две строки.
# Читаем входной файл
with open('26.txt', 'r', encoding='utf-8') as f:
# Первая строка — параметры (N, лимит времени и т.п.)
N, T = map(int, f.readline().split())
data = []
for i in range(N):
parts = f.readline().split()
# Подстраиваем под формат: обычно (длительность, ценность)
t, v = int(parts[0]), int(parts[1])
data.append({'id': i + 1, 't': t, 'v': v})
# Сортируем по нужному критерию (тут — по убыванию плотности v/t)
data.sort(key=lambda x: (-x['v'] / x['t'], x['id']))
# Жадный проход
total_time = 0
total_value = 0
taken = []
for item in data:
if total_time + item['t'] <= T:
total_time += item['t']
total_value += item['v']
taken.append(item['id'])
print(total_value, len(taken))
Этот код решает задачу «успеть максимум дел за время T». Замени строку сортировки и условие внутри цикла — получишь решение для любого типа из четвёрки выше.
Полный пример. «Выбрать N заданий с максимальной ценностью»
Разберём задачу целиком, чтобы стало понятно, как критерий сортировки влияет на ответ.
Условие
В школе прошёл хакатон. У организаторов есть список из N заданий (до 10 000). Для каждого задания известны:
- длительность в минутах
t(от 5 до 300), - ценность
v— сколько баллов команда получит за его выполнение (от 10 до 1000).
У команды есть T минут (обычно 480 — 8 часов). Команда не может прерывать задание, раз уж начала. Команда хочет набрать максимальную суммарную ценность.
Найди эту максимальную ценность и количество выбранных заданий — это и есть те два числа, которые пойдут в ответ.
Формат файла
10000 480
12 150
45 720
8 90
...
Первая строка — N и T, дальше N строк с парами (t, v).
Разбор
Почему сортировка по v/t, а не по v? Возьмём на пальцах три задания и T = 30:
| ID | t | v | v/t |
|---|---|---|---|
| 1 | 20 | 100 | 5.0 |
| 2 | 10 | 60 | 6.0 |
| 3 | 15 | 75 | 5.0 |
Сортировка по убыванию v даст последовательность [1, 3, 2] → берём 1 (10 минут осталось), 3 не влезает (15 > 10), берём 2 → итого 100 + 60 = 160. Успели 2 задания.
Сортировка по убыванию v/t даст [2, 1, 3] → берём 2 (20 минут осталось), берём 1 (осталось 0), 3 не влезает → итого 60 + 100 = 160. То же самое? В этом примере — да, потому что обе жадности уложились в 30 минут.
А теперь T = 25. По v → берём 1 (осталось 5), 3 не влезает, 2 не влезает → 100. По v/t → берём 2 (осталось 15), берём 3 (осталось 0) → 60 + 75 = 135. Вот где критерий v/t обгоняет.
Плотность отражает, сколько ценности приносит минута времени. Если ты берёшь задания в порядке от самого «плотного» — ты максимально эффективно используешь каждую минуту.
Код решения
def solve(filename):
with open(filename, 'r', encoding='utf-8') as f:
first = f.readline().split()
N, T = int(first[0]), int(first[1])
tasks = []
for i in range(N):
t_str, v_str = f.readline().split()
t = int(t_str)
v = int(v_str)
tasks.append((t, v, i + 1))
# Сортируем по убыванию v/t, при равной плотности — по возрастанию ID
tasks.sort(key=lambda x: (-x[1] / x[0], x[2]))
time_left = T
total_value = 0
count = 0
for t, v, task_id in tasks:
if t <= time_left:
time_left -= t
total_value += v
count += 1
return total_value, count
value, count = solve('26.txt')
print(value, count)
Сложность — O(N log N): даже на десятках тысяч записей код отрабатывает за доли секунды.
На что смотреть при проверке ответа
- Выводишь то, что просят — ценность и количество, а не наоборот; порядок двух чисел в ответе задаётся условием.
- Осталось меньше минимальной длительности — если у тебя после жадности осталось ещё 20 минут свободных, но все оставшиеся задачи длиннее 20 минут — всё нормально, это предел жадного подхода.
- Ответ правдоподобен — прикинь порядок величин: суммарная ценность не может превышать сумму всех ценностей в файле.
Почему решение обязано быть быстрым
Задание 26 нельзя взять «в лоб» — объём данных подобран так, чтобы отсечь неэффективные подходы:
| Подход | N = 1000 | N = 100 000 |
|---|---|---|
| Полный перебор подмножеств | не успеет | не успеет |
| O(N²) двойной цикл | ~0.5 сек — OK | часы — не успеет |
| O(N log N) сортировка | 0.01 сек | 0.1 сек — OK |
| ДП по таблице N×T | зависит от T | зависит от T |
Вывод: всегда пиши O(N log N) с сортировкой — это единственный подход, который гарантированно доживёт до ответа.
Типовые «ломающие» детали на больших данных
- Большие числа — если ценность до 10^9, не забывай, что Python умеет большие числа нативно, но на C++ получишь переполнение в
int. - Одинаковые значения — на десятках тысяч записей почти гарантированно встречаются задания с одинаковой плотностью. Без вторичного ключа при равной плотности элементы останутся в исходном порядке файла, а условие обычно требует конкретный порядок разрешения ничьей (например, меньший ID) — получишь неверный ответ и даже не заметишь этого.
- Флоат-сравнения — если сортируешь по
v/t, из-за ошибок округления жадность может пойти не туда. Лечится умножением на знаменатель: сравнивайv1 * t2сv2 * t1вместоv1/t1сv2/t2.
# Надёжнее, чем v/t — сравниваем без флоатов
from functools import cmp_to_key
def compare(a, b):
# a и b — кортежи (t, v, id)
left = a[1] * b[0] # v_a * t_b
right = b[1] * a[0] # v_b * t_a
if left > right:
return -1
if left < right:
return 1
return a[2] - b[2]
tasks.sort(key=cmp_to_key(compare))
Но в подавляющем большинстве задач ЕГЭ v/t через float работает нормально — числа не настолько близкие, чтобы флоат врал.
Типичные ошибки на задании 26
Ошибка 1. Неверный критерий сортировки
Самая распространённая. Сортируют по ценности, а надо по плотности. Или по длительности (чтобы «успеть больше задач» — но это даёт малое количество дорогих заданий). Лечится тестом на малом примере вручную: возьми 4-5 записей, найди оптимум перебором, сравни с жадностью. Если сходится — критерий верный.
Ошибка 2. Перепутан порядок чисел в ответе
Ответ в задании 26 — два числа в заданном порядке. Если условие просит «наибольшую ценность, а затем количество», а ты записал наоборот — проверяющая система засчитает в лучшем случае одно совпадение. Перед вводом ответа перечитай последнее предложение условия и сверь порядок.
Ошибка 3. Путаница int и float
# ПЛОХО: total_value — float, ответ принимается только как int
total_value = 0.0
# ХОРОШО
total_value = 0
Если в условии сказано «вывести целое число» и ты выводишь 123.0 — ответ может не зачесть строгая проверка. Приводи через int() или считай в int с самого начала.
Ошибка 4. Забыл про первую строку файла
В большинстве задач первая строка — это параметры (N, T, W — что угодно). Если ты сразу начнёшь читать её как данные, у тебя съедет вся последующая обработка. Всегда отдельно читай первую строку.
Ошибка 5. Неверная обработка строковых полей
Иногда в файле приходят не числа, а строки-идентификаторы (A0012, BC17). Их нельзя переводить в int — сравнивай как строки или как хеши. Если в условии просят отсортировать по ID как по строке — используй sorted(..., key=lambda x: x['id']) без преобразований.
Сколько времени закладывать на экзамене
КЕГЭ длится 235 минут. Разбивка, которая работает у 90-балльников:
| Блок | Заданий | Время |
|---|---|---|
| 1-10 | 10 | 40-50 мин |
| 11-20 | 10 | 60-80 мин |
| 21-25 | 5 | 40-50 мин |
| 26 | 1 | 30-40 мин |
| 27 | 1 | 40-50 мин |
| Проверка | — | 20-30 мин |
Если на 26 тратишь больше 40 минут — впиши то число, в котором уверен, и переходи к 27: одно верное число из двух даёт 1 балл, а 27-е стоит ещё 2. Промахнуться с таймингом хуже, чем недобрать балл здесь.
Если перед экзаменом хочешь выстроить план подготовки целиком — посмотри план на 3 месяца или на 6 месяцев. Там задания 26-27 занимают отдельную неделю каждое.
Как тренироваться
Шаг 1. Освой шаблон
Возьми шаблон из этой статьи (раздел «Полный шаблон решения»). Адаптируй под все 4 типа задач из раздела «Типовые формулировки». Напиши 4 версии — по одной для каждого типа. После этого у тебя в голове будет «словарь критериев сортировки».
Шаг 2. Прорешай по 5 вариантов каждого типа
Где брать варианты:
- ФИПИ — открытый банк (есть задания 26 прошлых лет).
- Поляков-сайт (kpolyakov.spb.ru) — сотни задач с автопроверкой.
- Тренажёр TuteMe — задания с автопроверкой и разборами, в которых объяснён выбор критерия сортировки.
На каждом прорешанном варианте фиксируй: какой тип, какой критерий, за сколько минут решил. К 10-му варианту у тебя выработается чутьё на тип задачи уже по формулировке.
Шаг 3. Тренируйся на времени
Поставь таймер на 40 минут. Возьми задание 26 и реши его полностью — включая время на чтение условия, отладку и ввод обоих чисел ответа. В 30-35 минут должен укладываться даже на первом раунде. Если медленнее — вернись к шагу 2.
Шаг 4. Разбор ошибок
После каждого неправильного ответа не смотри решение сразу. Попробуй найти ошибку сам: печатай промежуточные результаты, сравнивай с тестовыми данными из условия (они всегда даются). Если за 15 минут не нашёл — смотри разбор. Но собственный разбор ценнее для памяти.
Шире про навыки подготовки — в разборе демоверсии ЕГЭ 2026 и статье об изменениях в ЕГЭ 2026.
Чек-лист перед тем, как сдавать задание 26
- Прочитал условие дважды и понял, какие два числа требуется вывести и в каком порядке.
- Определил тип задачи: «успеть дела» / «расписание» / «K-й по порядку» / «рюкзак».
- Выбрал критерий сортировки. Сверил на мини-примере 4-5 элементов.
- Убедился, что решение — O(N log N), без вложенных циклов по всем парам.
- Прогнал код и сверил с проверочным примером из условия (если дан).
- Вписал оба числа в ответ в правильном порядке.
Коротко главное
- Задание 26 стоит 2 балла; ответ — два числа: оба верны — 2 балла, одно — 1.
- Объём данных большой, поэтому решение обязано быть O(N log N).
- Как правило, решение — это правильная сортировка + жадный проход.
- Критерий сортировки — главная интеллектуальная часть задачи. Всегда проверяй на малом примере.
- Используй Python и
sorted(key=lambda x: ...)с кортежем из нескольких ключей. - Порядок двух чисел в ответе — по условию; перепутаешь — потеряешь балл.
- Тайминг на экзамене — 30-40 минут, не больше.
Если пока спотыкаешься на более ранних задачах — сначала доведи до автоматизма задание 17 (чтение файла и обработка массива): это тот же навык, только без жадности и на меньших объёмах. К заданию 26 возвращайся, когда уверенно решаешь всё до 25-го.
Все четыре типа задания 26 есть в TuteMe с автопроверкой: большие файлы, разбор с критерием сортировки и редактор Python прямо в браузере.