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

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

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

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

Задание входит в блок практического программирования и требует не теоретических знаний, а умения быстро и без ошибок реализовать несложный алгоритм на выбранном языке программирования (Pascal, Python, C++, Basic — допускается любой).

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

Типичная формулировка звучит так: «В файле содержится последовательность целых чисел. Элементы последовательности могут принимать значения от $-10000$ до $10000$ включительно. Определите и запишите в ответе сначала количество пар элементов, удовлетворяющих условию, затем максимальную из сумм элементов таких пар».

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

• диапазон значений чисел (например, от $-10000$ до $10000$ или натуральные числа до $10000$);
• количество элементов в последовательности (часто $10000$, но может быть и другое число, оно не всегда указано явно и определяется чтением файла до конца);
• тип пары — «два идущих подряд элемента» или «два различных элемента, порядок не важен»;
• условие на пару — делимость на число, чётность/нечётность, различие или совпадение остатков от деления, диапазон значений и т. п.

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

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

• Делимость числа $a$ на $m$: $a \bmod m = 0$.
• Остаток от деления: $r = a \bmod m$, где $0 \le r < m$ для натуральных чисел; при проверке на равенство нулю знак числа не важен ни в одном языке программирования.
• Число пар без повторов из $n$ элементов: $C_n^2 = \dfrac{n(n-1)}{2}$.
• Пара соседних элементов последовательности $a_1, a_2, \dots, a_n$ — это $(a_i, a_{i+1})$ при $i = 1, \dots, n-1$; всего таких пар $n-1$.
• Логическое «хотя бы одно из двух» — это операция ИЛИ (or), «оба одновременно» — операция И (and).
• Разность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность: $a - b \equiv 0 \pmod 2 \iff a \bmod 2 = b \bmod 2$.
• Сложность полного перебора всех пар из $n$ элементов — $O(n^2)$; при $n = 10000$ это порядка $5 \cdot 10^7$–$10^8$ операций.
• Числа в файле обычно записаны через пробел или каждое на отдельной строке — язык программирования должен уметь читать оба формата.

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

1. Метод последовательного просмотра (для соседних пар). Если пара — это два идущих подряд элемента, достаточно одного цикла: пройти по последовательности от первого элемента до предпоследнего и на каждом шаге сравнить $a_i$ и $a_{i+1}$. Сложность $O(n)$.

Мини-пример: для последовательности $6, 2, 9, -3, 6$ пары соседей — $(6,2), (2,9), (9,-3), (-3,6)$, всего $n-1=4$ пары.

2. Метод полного перебора всех пар (для произвольных пар). Когда пара — любые два различных элемента без учёта порядка, используют два вложенных цикла: внешний по индексу $i$ от $0$ до $n-1$, внутренний по индексу $j$ от $i+1$ до $n-1$. Так каждая пара учитывается ровно один раз, число пар равно $C_n^2$.

Мини-пример: для трёх чисел $2, 5, 7$ пары — $(2,5), (2,7), (5,7)$, то есть $C_3^2 = 3$.

3. Метод группировки по остаткам или по делимости. Если условие связано с остатком от деления на фиксированное небольшое число $d$ или $p$, можно заранее разложить числа по «корзинам» — спискам чисел с одинаковым остатком. Это ускоряет анализ при больших $n$ и небольшом $d$, так как позволяет свести сравнение всех пар к сравнению корзин.

Мини-пример: для $d=3$ числа $6, 2, 9, -3$ распределятся по остаткам $0, 2, 0, 0$ — три числа попадают в корзину «остаток 0».

4. Метод раздельных счётчиков и максимумов по категориям. Условие «хотя бы одно из чисел делится на $p$» удобно обрабатывать, разбив все числа на две группы: делящиеся на $p$ и не делящиеся. Тогда искомые пары — это все пары внутри первой группы плюс все пары между первой и второй группой; максимум суммы ищется отдельно в каждой из этих категорий пар.

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

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

1. Определить формат входных данных: сколько чисел, в каком диапазоне, как они разделены в файле.
2. Прочитать все числа в список (массив) или организовать построчное/поточное чтение.
3. Внимательно выделить тип пары — соседние элементы или произвольные два различных элемента без учёта порядка.
4. Сформулировать условие на пару в виде логического выражения на языке программирования, точно повторяя формулировку задания (союз «и» — это and, «хотя бы одно» — это or).
5. Организовать цикл (один — для соседних пар, два вложенных — для произвольных пар), на каждом шаге проверять условие.
6. При выполнении условия увеличивать счётчик количества пар и сравнивать сумму пары с текущим максимумом, обновляя его при необходимости.
7. После завершения цикла вывести два числа: количество и максимальную сумму, разделённые пробелом.
8. Проверить решение на приведённом в условии примере входных данных, если он есть — это лучший способ убедиться в правильности программы до отправки на большом файле.

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

Пример 1. Последовательность целых чисел от $-10000$ до $10000$. Пара — два идущих подряд элемента. Нужно найти количество пар, где хотя бы одно число делится на $3$, и максимальную сумму среди таких пар.

Шаг 1. Читаем все числа в список seq.

Шаг 2. Так как пара — это соседние элементы, используем один цикл по индексу i от 0 до len(seq)-2.

Шаг 3. Условие: a % 3 == 0 or b % 3 == 0, где a = seq[i], b = seq[i+1]. Проверка на равенство нулю работает верно независимо от знака числа.

Шаг 4. Код на Python:

seq = list(map(int, open('input.txt').read().split()))
count = 0
max_sum = None
for i in range(len(seq) - 1):
    a, b = seq[i], seq[i + 1]
    if a % 3 == 0 or b % 3 == 0:
        count += 1
        s = a + b
        if max_sum is None or s > max_sum:
            max_sum = s
print(count, max_sum)

Шаг 5. Проверка на примере из условия: последовательность $6, 2, 9, -3, 6$. Пары соседей: $(6,2)$ — $6$ делится на $3$, подходит, сумма $8$; $(2,9)$ — $9$ делится на $3$, подходит, сумма $11$; $(9,-3)$ — оба делятся на $3$, подходит, сумма $6$; $(-3,6)$ — оба делятся на $3$, подходит, сумма $3$. Итого $4$ пары, максимальная сумма $11$ — совпадает с примером из условия («4 11»).

Шаг 6. На реальном файле с $10000$ элементами эта программа выполнится мгновенно, так как сложность линейна: $O(n)$. Ответ для полного файла — «2802 1990».

Пример 2. Последовательность из $10000$ натуральных чисел, каждое не больше $10000$. Пара — два различных элемента, порядок не важен. Условие: остатки от деления на $d=160$ различны И хотя бы одно число делится на $p=7$.

Шаг 1. Читаем числа в список seq, длина n = len(seq).

Шаг 2. Так как пара — произвольные различные элементы без учёта порядка, нужны два вложенных цикла: внешний по i от 0 до n-1, внутренний по j от i+1 до n-1.

Шаг 3. Условие для пары (a, b): a % 160 != b % 160 and (a % 7 == 0 or b % 7 == 0).

Шаг 4. Код на Python:

seq = list(map(int, open('input.txt').read().split()))
n = len(seq)
count = 0
max_sum = None
for i in range(n):
    for j in range(i + 1, n):
        a, b = seq[i], seq[j]
        if a % 160 != b % 160 and (a % 7 == 0 or b % 7 == 0):
            count += 1
            s = a + b
            if max_sum is None or s > max_sum:
                max_sum = s
print(count, max_sum)

Шаг 5. Проверка на примере из условия: числа $168, 320, 328, 7$. Остатки от деления на $160$: $168 \bmod 160 = 8$, $320 \bmod 160 = 0$, $328 \bmod 160 = 8$, $7 \bmod 160 = 7$. Делимость на $7$: $168$ делится, $320$ не делится, $328$ не делится, $7$ делится.

Перебираем все $6$ пар: $(168,320)$ — остатки $8$ и $0$ различны, $168$ делится на $7$ — подходит, сумма $488$; $(168,328)$ — остатки $8$ и $8$ совпадают — не подходит; $(168,7)$ — остатки $8$ и $7$ различны, оба делятся на $7$ — подходит, сумма $175$; $(320,328)$ — остатки $0$ и $8$ различны, но ни одно не делится на $7$ — не подходит; $(320,7)$ — остатки различны, $7$ делится на $7$ — подходит, сумма $327$; $(328,7)$ — остатки различны, $7$ делится на $7$ — подходит, сумма $335$. Итого $4$ подходящие пары, максимальная сумма $488$ — совпадает с примером («4 488»).

Шаг 6. Замечание по сложности: при $n=10000$ двойной цикл делает около $5 \cdot 10^7$ итераций — на Python это может занять десятки секунд, поэтому на реальном экзамене лучше использовать более быстрый язык (Pascal, C++) или предварительно сгруппировать числа по остаткам, чтобы снизить число сравнений. Итоговый ответ на полном файле — «12749665 19989».

Пример 3. Последовательность из $10000$ положительных целых чисел, каждое не больше $10000$. Пара — два различных элемента, порядок не важен. Условие: разность чётна И хотя бы одно число делится на $31$.

Шаг 1. Заметим, что «разность двух чисел чётна» равносильно тому, что оба числа имеют одинаковую чётность: $a \bmod 2 = b \bmod 2$. Это упрощает проверку.

Шаг 2. Код на Python:

seq = list(map(int, open('input.txt').read().split()))
n = len(seq)
count = 0
max_sum = None
for i in range(n):
    for j in range(i + 1, n):
        a, b = seq[i], seq[j]
        if a % 2 == b % 2 and (a % 31 == 0 or b % 31 == 0):
            count += 1
            s = a + b
            if max_sum is None or s > max_sum:
                max_sum = s
print(count, max_sum)

Шаг 3. Логика та же, что и в примере 2: два вложенных цикла перебирают все различные пары без повторов, для каждой пары проверяется составное условие «одинаковая чётность и делимость хотя бы одного числа на 31». Итоговый ответ для полного файла — «1569269 19982».

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

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

• Путаница между «соседними» и «произвольными» парами — из-за этого выбирается неверная структура цикла и получается совершенно другой (обычно намного больший) счётчик пар.
• Учёт пары элемента с самим собой при произвольных парах: внутренний цикл должен начинаться с j = i + 1, а не с j = i, иначе элемент образует пару с собой, что противоречит условию «два различных элемента».
• Двойной учёт одной и той же пары: если перебирать j от 0 до n-1 без ограничения j > i, каждая пара считается два раза, что искажает и количество, и не влияет на максимум, но портит первое число ответа.
• Ошибка off-by-one при построении пар соседних элементов: цикл должен идти до n-2 (индекс) или n-1 раз, а не до n-1 включительно, иначе возникнет выход за границы массива.
• Перепутывание «и» и «или»: условие «хотя бы одно из чисел делится на p» — это or, а «оба числа удовлетворяют условию» — это and; ошибка здесь меняет ответ радикально.
• Неверная трактовка «различные остатки»: нужно явно сравнивать a % d != b % d, а не путать это с условием неделимости на d.
• Забывание, что переменная максимума должна инициализироваться специальным значением (например, None в Python или очень маленьким числом в других языках), а не нулём — иначе при всех отрицательных суммах результат окажется неверным.
• Неучёт объёма данных: при $n=10000$ и вложенных циклах $O(n^2)$ на интерпретируемых языках программа может работать слишком долго; в компилируемых языках (Pascal, C++) такой перебор укладывается в разумное время.
• Переполнение типов данных в языках со статической типизацией: сумма двух чисел до $10000$ по модулю не переполняет integer, но если складывается много элементов или используются другие масштабы — стоит проверять диапазон типа.
• Невнимательное чтение формулировки о диапазоне значений: отрицательные числа требуют аккуратной проверки делимости, хотя сама проверка a % m == 0 не зависит от знака в подавляющем большинстве языков.

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

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

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

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

Полезно также заранее продумать, на каком языке решать это задание быстрее и увереннее: если предпочтителен Python, стоит помнить о возможной медлительности вложенных циклов при больших объёмах данных и по возможности заранее знать способы группировки чисел по остаткам для ускорения; если выбран Pascal или C++, вложенные циклы для $n=10000$ выполняются практически мгновенно, и можно сосредоточиться исключительно на правильности логики условия.

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