17. Числовые последовательности: #297026

Элементы пары не обязаны стоять рядом. Нужно рассмотреть любые два различных элемента последовательности, причём порядок элементов в паре не важен.

Сумма двух чисел делится на $7$, если их остатки от деления на $7$ дополняют друг друга до $7$.

Поэтому возможны следующие сочетания остатков: $0+0$, $1+6$, $2+5$, $3+4$.

Подсчитаем количество чисел с каждым остатком:

• $0$ — $1415$ чисел;
• $1$ — $1421$ число;
• $2$ — $1390$ чисел;
• $3$ — $1467$ чисел;
• $4$ — $1454$ числа;
• $5$ — $1450$ чисел;
• $6$ — $1403$ числа.

Для остатка $0$ выбираем любые два различных элемента: $\dfrac{1415\cdot1414}{2}=1000405$.

Для остальных остатков перемножаем количества элементов соответствующих групп:

$1421\cdot1403=1993663$,
$1390\cdot1450=2015500$,
$1467\cdot1454=2133018$.

Общее количество подходящих пар: $1000405+1993663+2015500+2133018=7142586$.

Теперь найдём максимальную сумму.

Максимальная подходящая пара — $9998$ и $9994$. Оба числа присутствуют в файле.

Проверим остатки:

$9998\bmod7=2$,
$9994\bmod7=5$.

Следовательно, $(9998+9994)\bmod7=0$.

Сумма: $9998+9994=19992$.

Код на Python

a = [int(x) for x in open('17-30.txt')]

groups = [[] for _ in range(7)]

for x in a:
    groups[x % 7].append(x)

count = (
    len(groups[0]) * (len(groups[0]) - 1) // 2
    + len(groups[1]) * len(groups[6])
    + len(groups[2]) * len(groups[5])
    + len(groups[3]) * len(groups[4])
)

groups[0].sort(reverse=True)

max_sum = max(
    groups[0][0] + groups[0][1],
    max(groups[1]) + max(groups[6]),
    max(groups[2]) + max(groups[5]),
    max(groups[3]) + max(groups[4])
)

print(count, max_sum)

Программа выводит:

7142586 19992