Задание 26 ЕГЭ по информатике: обработка целочисленной информации

Что проверяет задание

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

Как выглядит формулировка и сколько баллов

Сюжет обычно бытовой: архивация файлов, распределение ресурсов, обработка показаний датчиков. Во входном файле в первой строке даны параметры — например $S$ (ограничение) и $N$ (количество элементов, до 1000–5000), затем в $N$ строках идут сами числа $a_1, a_2, \dots, a_N$ (обычно натуральные, не больше 100). Нужно вывести одно или два числа-ответа: например, максимальное количество элементов, которые можно уместить в ограничение, и дополнительный параметр (максимальный или минимальный элемент в этом наборе). Задание оценивается в 2 балла — по одному баллу за каждое верно найденное число.

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

• $S$ — ограничение (объём диска, лимит времени, вместимость); $N$ — количество элементов; $a_1,\dots,a_N$ — значения.
• Префиксная сумма отсортированного по возрастанию массива: $P_k = a_{(1)}+a_{(2)}+\dots+a_{(k)}$.
• Монотонность: если массив отсортирован по возрастанию, $P_k$ не убывает при росте $k$, поэтому можно искать максимальное допустимое $k$ простым проходом или бинарным поиском.
• Условие допустимости набора из $k$ элементов: $P_k \le S$.
• Жадный принцип: чтобы вместить максимум элементов при ограничении суммы, берут наименьшие по значению элементы.
• Чтобы максимизировать «верхний» элемент в наборе при фиксированном $k$, используют метод последовательных замен наименьшего выбранного элемента на следующий по величине из оставшихся, если сумма остаётся $\le S$.
• Резерв после набора: $R = S - P_k$ — показывает, сколько «свободного места» остаётся для возможных замен.
• Суммарный объём данных редко превышает разумные пределы (например, $5000 \times 100 = 500000$), но тип переменной для суммы стоит выбирать с запасом.

Методы решения

1. Сортировка + жадный набор для максимизации количества элементов. Сортируем массив по возрастанию и накапливаем сумму, пока она не превысит $S$ — число накопленных элементов и есть максимальное $k$. Мини-пример: $S=100$, числа 80, 30, 50, 40. После сортировки: 30, 40, 50, 80. $P_1=30$, $P_2=70$, $P_3=120>100$ — значит $k=2$.

2. Метод замен для максимизации значения в наборе. После нахождения $k$ отобраны $k$ наименьших элементов (минимальная сумма при этом $k$). Чтобы получить набор с максимально возможным верхним элементом, пробуем заменить наименьший выбранный элемент на следующий по возрастанию из невыбранных, если новая сумма не превышает $S$. Пример: набор {30,40}, сумма 70. Заменяем 30 на 50: сумма $70-30+50=90\le100$ — допустимо, максимум стал 50.

3. Бинарный поиск по $k$. Для больших $N$ удобно искать максимальное допустимое $k$ бинарным поиском по отсортированному массиву префиксных сумм, это ускоряет проверку условия $P_k\le S$ до $O(\log N)$ на каждый запрос.

4. Метод скользящего окна (два указателя). Применяется, если элементы нужно брать подряд (например, последовательные показания датчика), а не в произвольном порядке — окно расширяется и сужается, поддерживая сумму в пределах $S$.

5. Полный перебор на малых $N$. Для отладки логики на маленьких придуманных наборах (5–10 чисел) полезно вручную перебрать все подмножества и убедиться, что жадный алгоритм даёт тот же ответ, что и перебор.

Алгоритм решения по шагам

1. Прочитать первую строку файла: значения $S$ и $N$.
2. Прочитать $N$ чисел в массив.
3. Отсортировать массив по возрастанию.
4. Накапливать сумму по возрастанию элементов, пока она не превысит $S$; число накопленных элементов — первый ответ $k$.
5. Зафиксировать сумму $P_k$ и текущий набор (первые $k$ элементов).
6. Для второго ответа применить метод замен: пытаться заменить наименьший элемент текущего набора на следующий недобранный элемент, если после замены сумма остаётся $\le S$; повторять, пока находятся выгодные замены.
7. Вывести два числа в требуемом порядке: количество элементов и найденный оптимальный параметр (например, максимальный размер файла).

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

Рассмотрим демонстрационные данные из условия, на которых строится логика всех вариантов задания: $S=100$, $N=4$, файлы 80, 30, 50, 40.

Шаг 1. Сортировка по возрастанию: 30, 40, 50, 80.

Шаг 2. Накопление суммы: $P_1=30\le100$; $P_2=70\le100$; $P_3=120>100$. Значит максимальное число пользователей $k=2$.

Шаг 3. Текущий набор — {30,40}, сумма 70, максимум в наборе — 40.

Шаг 4. Метод замен: заменяем наименьший элемент набора (30) на следующий недобранный (50): новая сумма $70-30+50=90\le100$ — допустимо, максимум становится 50, набор {40,50}.

Шаг 5. Пробуем заменить 40 на 80: новая сумма $90-40+80=130>100$ — недопустимо, замена не выполняется.

Итог: $k=2$, максимальный сохранённый файл — 50. Ответ «2 50» совпадает с условием.

Именно такой алгоритм — сортировка, накопление суммы, последовательные замены — применяется к реальным входным файлам, где $N$ достигает 1000, 4000 и 5000 значений. После обработки полного набора программа выдаёт следующие результаты для трёх вариантов задания:

• Вариант с $N\le1000$: ответ $k=568$, максимальный файл $=50$.
• Вариант с $N\le4000$: ответ $k=611$, максимальный файл $=27$.
• Вариант с $N\le5000$: ответ $k=397$, максимальный файл $=17$.

Большие значения $k$ получаются потому, что среди тысяч файлов много мелких значений (от 1 до 100), и после сортировки первые сотни элементов укладываются в лимит $S\le10000$. Второе число показывает, насколько крупный файл можно позволить включить в оптимальный набор без потери количества $k$: оно находится тем же методом замен, что и в демонстрационном примере, только замен там значительно больше из-за объёма данных.

Логику второго числа можно описать формально: если после сортировки первые $k$ элементов дают сумму $P_k\le S$, а $k{+}1$-й элемент уже не помещается ($P_k+a_{k+1}>S$), то резерв $R=S-P_k$ показывает свободное место. Если среди недобранных элементов есть $a_j$ ($j>k$) такой, что $a_j-a_{\min}\le R$, где $a_{\min}$ — наименьший элемент текущего набора, замена выгодна и увеличивает максимум набора без потери количества файлов. Программа перебирает такие возможности одну за другой, пока замены не перестают давать выигрыш — так получаются итоговые числа 50, 27 и 17 в трёх вариантах.

Типичные ошибки и ловушки

• Сортировка в неверном порядке: для максимизации количества элементов нужно сортировать по возрастанию, а не по убыванию.
• Наивный вывод максимума из первых $k$ наименьших элементов без метода замен — это даёт заниженный второй ответ (40 вместо 50 в примере выше).
• Остановка после одной удачной замены: нужно повторять процесс, пока находятся выгодные варианты, иначе результат окажется неоптимальным.
• Ошибки при чтении входного файла: путаница порядка $S$ и $N$ в первой строке, неверное количество считанных строк.
• Переполнение переменных при суммировании большого количества элементов — стоит проверять диапазон типа данных в выбранном языке.
• Выход за границы массива при переборе кандидатов на замену (особенно на последнем элементе).
• Неверный порядок чисел в ответе: сначала количество, затем оптимальный параметр, а не наоборот.

Как готовиться

• Освоить сортировку массивов и чтение файлов на выбранном языке программирования (Python, Pascal или C++).
• Прорешать несколько вариантов задания 26 с разными сюжетами, выделяя общий шаблон: сортировка, накопление суммы, жадные замены.
• Перед запуском на полном входном файле проверять программу на демонстрационном примере из условия.
• Обязательно тестировать граничные случаи: когда ни один элемент не помещается ($k=0$) и когда помещаются все элементы ($k=N$).
• Добавлять в код промежуточные выводы для отладки (текущая сумма, текущий максимум, число выбранных элементов) и убирать их перед финальной сдачей.
• Тренироваться считать вручную на маленьких придуманных наборах (5–10 чисел), чтобы закрепить логику метода замен.
• Разбирать готовые типовые решения построчно, понимая назначение каждой части кода, а не просто копировать шаблон.