Задание 27 ЕГЭ по информатике: кластеризация чисел и обработка больших файлов

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

Задание 27 — практическое программирование, где нужно написать программу, обрабатывающую поток числовых данных и вычисляющую заданную величину (сумму, произведение, количество пар и т.п.) по правилу, связанному с делимостью или остатками. Проверяются: умение переводить словесное условие в алгоритм; знание базовых структур данных (массивы, счётчики, частотные таблицы); умение оценивать сложность алгоритма и писать эффективные (обычно линейные) решения, способные обработать до $10^5$ элементов за разумное время; аккуратность в целочисленной арифметике. Ключевая идея большинства таких задач — кластеризация: разбиение чисел на несколько групп по общему признаку (остаток от деления, тип делимости на простые множители модуля), чтобы заменить полный перебор пар агрегированными вычислениями по группам.

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

Типичная формулировка: дана последовательность чисел или пар чисел (до $6\cdot10^4$–$10^5$ элементов), нужно вычислить сумму/произведение/количество пар, удовлетворяющих условию делимости или максимальности при ограничении. Входные данные — два файла: А (маленький, можно решить и перебором) и B (большой, переборный алгоритм не успеет отработать). В ответе указываются два числа — результат для файла А и для файла B, в этом порядке. За задание дают 2 балла: по одному за каждый файл, если программа выдаёт верный ответ и использует принципиально верный (не экспоненциальный) алгоритм. Достаточно приложить программу и итоговые числа — важен именно результат.

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

• Остаток от деления: $a \bmod m$ — число от $0$ до $m-1$, такое что $a = qm + (a\bmod m)$.
• Делимость: $a$ делится на $b$ тогда и только тогда, когда $a \bmod b = 0$.
• Разложение модуля на простые множители — ключ к решению: $14 = 2\cdot 7$, $26 = 2\cdot 13$.
• Произведение $x\cdot y$ делится на $p\cdot q$ (простые $p\ne q$), если множители $p$ и $q$ в сумме «набираются» у $x$ и $y$: одно число делится на $pq$, либо одно делится на $p$, другое — на $q$.
• Число пар внутри одной группы размера $k$: $\binom{k}{2} = \dfrac{k(k-1)}{2}$.
• Число пар между двумя разными группами размерами $k$ и $l$: $k\cdot l$.
• Сложность: полный перебор пар — $O(n^2)$, при $n=10^5$ это $10^{10}$ операций (слишком долго); проход с группировкой — $O(n)$ или $O(n\log n)$.
• При $n\le 10^5$ и элементах до $10^4$ сумма может достигать $10^9$, произведение — до $10^8$; в C++/Pascal нужен 64-битный тип, в Python переполнения нет.

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

1. Линейный проход с накоплением. Проходим по данным один раз, храня нужные агрегаты. Пример: для каждой пары выбрать большее и сложить — $S=\sum_{i=1}^n \max(a_i,b_i)$ вычисляется за один проход.

2. Кластеризация по остаткам. Разбиваем числа на группы по остатку от деления на модуль, связанный с условием (на 2, 3, 7, 13 и т.д.). Внутри каждой группы храним количество элементов, сумму, максимум или топ-несколько значений. Пример: для делимости на 26 получаем 4 кластера — «делится на 26», «делится на 13, не на 2», «делится на 2, не на 13», «прочие».

3. Жадная минимальная коррекция. Если оптимальная сумма не удовлетворяет дополнительному ограничению, ищем минимальное изменение, переводящее её в допустимое состояние. Пример: сумма максимумов $S\equiv 0\pmod 3$ — находим минимальную «потерю» $d=\max-\min$ среди пар, где $d\bmod 3\neq 0$, и меняем выбор именно в этой паре.

4. Топ-к элементов в кластере. Для поиска оптимальной комбинации (например, максимального произведения) при нескольких условиях делимости достаточно хранить 2–3 наибольших значения каждого типа и проверять только эти кандидаты.

5. Комбинаторный подсчёт пар по кластерам. Вместо перебора всех $\binom{n}{2}$ пар считаем количество валидных пар через размеры кластеров: внутри «подходящего» кластера — по формуле сочетаний, между «дополняющими» кластерами — произведением их размеров.

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

1. Прочитать входные данные: количество элементов $N$ и сами значения.
2. Определить признак, связанный с условием (остаток от деления или простые множители модуля из условия).
3. Завести переменные-агрегаты для каждого кластера (количество, сумма, максимум, топ-несколько значений).
4. Один раз пройти по элементам, распределяя каждый в соответствующий кластер и обновляя агрегаты.
5. По собранным агрегатам применить формулу задачи (суммирование, $k\cdot l$, $\binom{k}{2}$, минимальная коррекция, перебор top-k) — без обращения ко всему массиву.
6. Повторить для обоих файлов (маленький можно проверить и перебором) и вывести оба числа в требуемом порядке.

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

Пример 1 (максимальная сумма, не кратная 3). Из каждой пары выбираем число так, чтобы сумма была максимальна и не делилась на 3. Шаг 1. Для каждой пары берём $\max(a_i,b_i)$, считаем $S=\sum \max(a_i,b_i)$. Шаг 2. Если $S \bmod 3 \neq 0$ — это ответ. Шаг 3. Если $S \bmod 3 = 0$, заменяем в одной паре максимум на минимум, теряя $d_i=\max(a_i,b_i)-\min(a_i,b_i)$. Сумма $S-d_i$ не кратна 3, если $d_i \bmod 3 \neq 0$. Берём минимальное такое $d_i$. На данных из условия: пары $(1,3),(5,12),(6,9),(5,4),(3,3),(1,1)$. Максимумы: $3,12,9,5,3,1$, $S=33$, $33\bmod3=0$. Разности: $2,7,3,1,0,0$; остатки по модулю 3: $2,1,0,1,0,0$. Минимальная разность с ненулевым остатком — $d=1$ (пара $(5,4)$). Ответ: $33-1=32$ — совпадает с условием. Тот же алгоритм на файлах A и B даёт суммы $127127$ и $399762080$.

Пример 2 (наибольшее произведение, кратное 14). $14=2\cdot7$. Произведение делится на 14, если хотя бы одно число делится на 14 само, либо одно делится на 7 (не обязательно на 2), а другое — на 2 (не обязательно на 7). Шаг 1. Классифицируем каждое число: делится на 14; делится на 7, не на 2; делится на 2, не на 7; прочие. Шаг 2. Для группы «делится на 14» умножаем любое такое число на максимум из всех остальных. Шаг 3. Для комбинации «7, не 2» и «2, не 7» берём максимум каждой группы и умножаем. Шаг 4. Ответ — максимум из шагов 2–3. На примере из условия: числа $40,1000,7,28,55$. Число $28$ делится на 14, максимум среди остальных — $1000$, произведение $28\cdot1000=28000$ совпадает с демонстрационным ответом. Тот же метод на файлах A и B даёт $447552$ и $994000$.

Пример 3 (количество пар с произведением, кратным 26). $26=2\cdot13$. Кластеры: «кратно 26» ($k_{26}$), «кратно 13, не 2» ($k_{13}$), «кратно 2, не 13» ($k_2$), «прочие». Пары, дающие произведение кратное 26: пары с участием кластера 26 (считаются через общее число пар минус пары без него) плюс пары «13,не2» с «2,не13» — их количество $k_{13}\cdot k_2$. На маленьком примере: числа $2,6,13,39$. Кластер «кратно 26» пуст; «кратно 13, не 2» — $13,39$ ($k_{13}=2$); «кратно 2, не 13» — $2,6$ ($k_2=2$); произведение $k_{13}\cdot k_2=4$ совпадает с ответом из условия. Этот же метод на файлах A и B даёт $19$ и $199360639$.

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

• Полный перебор пар $O(n^2)$ на большом файле — программа не успевает выполниться, балл за файл B теряется.
• Переполнение целочисленного типа: суммы до $10^9$, произведения до $10^{10}$ — в C++/Pascal нужен long long/int64.
• Ошибка при определении «дополняющих» кластеров: число, кратное сразу двум множителям модуля, нельзя относить к кластеру «только один из множителей».
• Использование $k^2$ вместо $\binom{k}{2}=\dfrac{k(k-1)}{2}$ при подсчёте пар внутри одного кластера — результат завышается.
• В задачах на «максимум при ограничении» проверка только одной случайной коррекции вместо поиска минимальной по всем кандидатам.
• Путаница «пара различных элементов» с использованием одного элемента дважды.
• Отсутствие проверки программы на демонстрационном примере из условия перед запуском на большом файле.

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

Разбирайте задачи по единому шаблону: сначала определите признак делимости или остатка, лежащий в основе условия, затем продумайте, какие агрегаты (суммы, счётчики, максимумы) нужно хранить по кластерам вместо перебора всех элементов. Решайте «в две попытки» — сначала переборный вариант, проверенный на маленьком демонстрационном примере, затем эффективный алгоритм, сравнённый с тем же примером. Тренируйтесь оценивать сложность решения на бумаге: если при $n=10^5$ получается больше $10^7$–$10^8$ операций, алгоритм нужно переработать. Держите под рукой набор типовых модулей (2, 3, 7, 13, 14, 26 и их комбинации) и формул комбинаторики ($k\cdot l$, $\binom{k}{2}$). Регулярно решайте варианты прошлых лет именно этого номера, обращая внимание на пару «файл А — файл B»: если алгоритм одинаково быстро работает на обоих файлах, вы на верном пути.