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

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

Чтобы не перебирать около $50$ миллионов пар, будем обрабатывать числа последовательно и для каждого текущего числа $x$ искать подходящий второй элемент только среди уже просмотренных чисел. Тогда каждая пара будет учтена ровно один раз.

Сумма пары должна быть кратна $60$: $(x+y)\bmod60=0$.

Если остаток текущего числа $x$ от деления на $60$ известен, то для второго числа нужен остаток $(-x)\bmod60$.

Дополнительно хотя бы одно из двух чисел должно делиться на $40$.

Поэтому для каждого остатка от деления на $60$ будем хранить количество уже просмотренных чисел, а отдельно — количество чисел, которые ещё и делятся на $40$.

Если текущее число $x$ делится на $40$, то вторым элементом может быть любое ранее встреченное число с нужным остатком от деления на $60$.

Если текущее число $x$ не делится на $40$, то второе число обязательно должно делиться на $40$.

Для нахождения максимальной суммы аналогично будем хранить максимальное число с каждым остатком и максимальное число, кратное $40$, с каждым остатком.

После обработки всего файла получаем $29278$ подходящих пар.

Максимальная сумма равна $19860$. Она получается для элементов $9900$ и $9960$. Оба числа присутствуют в последовательности.

Проверим условия: $9960\bmod40=0$, то есть хотя бы один элемент пары делится на $40$.

Сумма элементов: $9900+9960=19860$.

Проверим кратность: $19860\bmod60=0$.

Следовательно, эта пара подходит.

Код на Python

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

cnt_all = [0] * 60
cnt_40 = [0] * 60

max_all = [0] * 60
max_40 = [0] * 60

count = 0
max_sum = 0

for x in a:
    r = (-x) % 60

    if x % 40 == 0:
        count += cnt_all[r]

        if max_all[r] != 0:
            max_sum = max(max_sum, x + max_all[r])
    else:
        count += cnt_40[r]

        if max_40[r] != 0:
            max_sum = max(max_sum, x + max_40[r])

    r = x % 60

    cnt_all[r] += 1
    max_all[r] = max(max_all[r], x)

    if x % 40 == 0:
        cnt_40[r] += 1
        max_40[r] = max(max_40[r], x)

print(count, max_sum)

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

29278 19860