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

В этой задаче пара — это не обязательно соседние элементы. Нужно рассмотреть любые два различных элемента последовательности. При этом пары $(x,y)$ и $(y,x)$ считаются одной и той же парой.

Перебирать все пары двумя вложенными циклами можно, но тогда придётся проверить почти $\dfrac{10,000\cdot9,999}{2}=49,995,000$ пар. Можно решить задачу значительно быстрее.

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

Чтобы сумма пары делилась на $80$, необходимо: $(x+y)\bmod80=0$. Если $x\bmod80=r$, то остаток второго числа должен быть $(-r)\bmod80$.

Будем хранить для каждого остатка от $0$ до $79$:

• количество уже просмотренных чисел с таким остатком;
• количество среди них чисел, кратных $50$;
• максимальное число с таким остатком;
• максимальное кратное $50$ число с таким остатком.

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

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

Так мы одновременно считаем количество подходящих пар и находим максимальную сумму.

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

Максимальная сумма получается для чисел $9910$ и $9850$. В файле встречаются оба этих элемента.

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

Сумма: $9910+9850=19760$.

Проверим кратность $80$: $19760\bmod80=0$.

Следовательно, максимальная сумма подходящей пары равна $19760$.

Код на Python

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

cnt_all = [0] * 80
cnt_50 = [0] * 80

max_all = [0] * 80
max_50 = [0] * 80

count = 0
max_sum = 0

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

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

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

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

    r = x % 80

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

    if x % 50 == 0:
        cnt_50[r] += 1
        max_50[r] = max(max_50[r], x)

print(count, max_sum)

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

21648 19760