Задание №17. Соседние пары и тройки: от условия к подсчёту

В файле дан длинный список чисел. Из него рассматриваются соседние пары или тройки, и для каждой группы проверяется одно и то же условие. Требуется посчитать подходящие группы и найти среди них наибольшее или наименьшее значение указанной величины. Часто правило отбора зависит от всего списка, поэтому решение начинается с поиска общего порога.

Что считается одной группой

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

Например, из фрагмента 53141, 10803, 77333 получаются две пары: (53141,10803) и (10803,77333). Среднее число участвует в обеих. Это перекрытие групп предусмотрено условием. Разбиение списка на непересекающиеся части пропустит часть пар.

Если чисел N, соседних пар N-1, а троек N-2: последнему началу группы должно хватить элементов до конца списка. Сортировка здесь недопустима, поскольку меняет соседство.

Полный пример: сумма двух остатков

В задаче с отбором по сумме остатков ↗ даны натуральные числа от 1 до 100000. Соседняя пара подходит, если сумма остатков обоих чисел при делении на 18 равна минимальному элементу всей последовательности. Требуются количество таких пар и максимальная сумма их элементов.

Файл и общий минимум

Из архива извлекается 319_17.txt. Он содержит 10000 чисел, по одному в строке; первая строка, 567, тоже является элементом последовательности. Заголовка с количеством элементов здесь нет. Начало настоящего файла выглядит так: 567, 51360, 76956, 45215,\ldots. Этот фрагмент показывает формат данных, но не заменяет весь файл.

По всем 10000 числам находится минимум: 8. Он расположен на позиции 9564 при отсчёте с единицы. Поэтому общий порог нельзя получить только из начала файла или менять по мере проверки пар: даже для первой пары нужен окончательный минимум всей последовательности.

Проверка пары и величина для ответа

Остаток при делении числа на 18 находится оператором Python %. Для первой пары остатки равны 567\bmod18=9 и 51360\bmod18=6. Их сумма 9+6=15 не равна 8. Пара не учитывается, и её сумма не участвует в поиске максимума.

У пары с началом на позиции 82 числа другие: 53141=18\cdot2952+5 и 10803=18\cdot600+3. Сумма остатков 5+3=8, поэтому пара подходит. Для ответа нужна уже сумма исходных чисел: 53141+10803=63944.

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

Программа для всего файла

Файл находится рядом с программой. Список a хранит числа в исходном порядке; t хранит общий минимум. Переменная count считает принятые пары, а best хранит лучшую найденную сумму. Значение None означает, что подходящая пара ещё не встретилась.

name = '319_17.txt'
enc = 'utf-8-sig'
with open(
    name, encoding=enc
) as f:
    a = []
    for line in f:
        if line.strip():
            n = int(line)
            a.append(n)

t = min(a)
count = 0
best = None
for i in range(len(a) - 1):
    x = a[i]
    y = a[i + 1]
    r = x % 18 + y % 18
    if r == t:
        count += 1
        s = x + y
        if best is None:
            best = s
        elif s > best:
            best = s
print(count, best)

Цикл чтения преобразует каждую непустую строку в целое число n и добавляет его в список. Кодировка utf-8-sig допускает служебную метку в начале текстового файла. Затем min(a) находит порог по всему списку. Проверка пар начинается лишь после этого.

В Python позиции списка отсчитываются с нуля. Цикл range(len(a) - 1) перебирает начала от нулевой позиции до предпоследней включительно. Числа x и y поэтому всегда существуют. Переменная r содержит сумму двух остатков; только при её равенстве порогу увеличивается счётчик и вычисляется сумма s. Первая принятая сумма становится начальным максимумом, последующие заменяют его, если они больше.

Результат и проверка

Программа проверяет 10000-1=9999 пар. Подходят 285. Наибольшую сумму даёт пара с началом на позиции 8579: 86120=18\cdot4784+8 и 80316=18\cdot4462. Её остатки дают 8+0=8, а сумма чисел равна 86120+80316=166436. Среди остальных подходящих пар большей суммы нет.

Ответ: 285 166436. Первый результат считает пары, второй относится к исходным числам принятой пары. Сумма остатков использовалась только для отбора.

Как меняется условие отбора

Сколько элементов имеют нужный признак

Для тройки начало цикла ограничивается range(len(a) - 2), а сама группа получается как a[i:i + 3]. Для слов «ровно одно» необходимо посчитать элементы с признаком. Например, в задаче с одним трёхзначным числом ↗ тройка 8756,-85,-442 содержит ровно одно такое число: -442. Количество цифр определяется без знака. Функция abs(x) возвращает модуль числа: для −442 это 442. В следующем фрагменте triple — проверяемая тройка, а k — счётчик трёхзначных элементов:

k = 0
for x in triple:
    if 100 <= abs(x) <= 999:
        k += 1

После проверки трёх элементов k становится равным 1. Обычная сумма тройки, со знаками, равна 8756-85-442=8229 и меньше порога 85917. Обе части условия выполнены. Слова «хотя бы один» означали бы k >= 1, а «не более двух» допускают значения 0, 1 и 2. Например, в условии с ограничением числа четырёхзначных элементов ↗ тройка -682,85871,-666 вообще не содержит четырёхзначных; это не мешает ей пройти проверку количества.

Что сравнивается и что запоминается

В задаче с квадратом суммы ↗ нужны ровно два двузначных числа и квадрат суммы меньше 99033. У тройки 325,80,-99 двузначны 80 и −99. Сначала получается сумма 325+80-99=306, затем её квадрат 306^2=93636<99033. Складывание квадратов каждого числа дало бы другое выражение и другой отбор.

В задаче с найденным делителем ↗ общий порог равен 105: это минимальное трёхзначное число последовательности, оканчивающееся на 5. У пары требуется ровно один трёхзначный элемент, а её сумма должна делиться на 105. Пара 100,5 подходит, потому что 100+5=105. Здесь после количества ищется минимальная сумма, поэтому при обновлении лучшего значения сравнение направлено в другую сторону.

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

Возможные ловушки

• Остаток суммы вместо суммы остатков. В основном примере ↗ складываются два отдельных остатка. Для учебной пары 17,9 их сумма равна 26, а остаток суммы при делении на 18 равен 8. Замена выражения ошибочно примет эту пару при пороге 8. Проверка записывается как x % 18 + y % 18.
• Положительность вместо числа цифр. В условии про трёхзначный элемент ↗ проверка без abs потеряет −442. Для разрядности используется модуль, но при сложении сохраняются знаки. Ноль при этом не является ни положительным, ни отрицательным.
• Минимальный модуль вместо минимального числа. В задаче с окончанием 15 ↗ минимальное подходящее трёхзначное число равно −915; его квадрат равен 837225. Окончание проверяется по abs(x) % 100, а минимум выбирается среди самих чисел. В тройке −192, −296, −4499 все числа одного знака; произведение её минимума и максимума равно (-4499)\cdot(-192)=863808>837225. Первый и последний элементы по позиции не заменяют минимум и максимум.
• Модуль до выбора максимума. В задаче с модулем итоговой суммы ↗ наибольшая принятая сумма равна 962. Модуль применяется после выбора этой суммы. Если сравнивать модули всех сумм, получится 195618: большое по модулю отрицательное число ошибочно станет «максимальным». Порядок двух действий сохраняется буквально.
• Начальный максимум, равный нулю. При отрицательных суммах ноль может оказаться больше каждой из них, хотя ни одной группе не соответствует. Значение None отделяет отсутствие результата от найденного числа. После полного обхода оно также позволяет заметить отсутствие подходящих групп.