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

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

Чтобы произведение двух чисел делилось на $10$, в произведении должны присутствовать множители $2$ и $5$.

Разобьём все числа на четыре группы:

• делятся на $10$;
• делятся на $2$, но не делятся на $5$;
• делятся на $5$, но не делятся на $2$;
• не подходят ни под одну из предыдущих групп.

В файле получаем:

• $980$ чисел, делящихся на $10$;
• $3965$ чисел, делящихся на $2$, но не на $5$;
• $1057$ чисел, делящихся на $5$, но не на $2$;
• $3998$ остальных чисел.

Если хотя бы одно число пары делится на $10$, вторым элементом может быть любое другое число последовательности.

Количество таких пар:

$980\cdot(10000-980)+\dfrac{980\cdot979}{2}$
$=980\cdot9020+479710$
$=8839600+479710$
$=9319310$.

Кроме того, подходят пары, в которых одно число делится на $2$, но не на $5$, а второе делится на $5$, но не на $2$.

Количество таких пар: $3965\cdot1057=4191005$.

Общее количество подходящих пар: $9319310+4191005=13510315$.

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

В последовательности есть число $10000$, которое делится на $10$.

Также в последовательности есть число $9999$.

Так как один из элементов пары равен $10000$, произведение этой пары обязательно делится на $10$.

Максимальная сумма: $10000+9999=19999$.

Код на Python

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

n = len(a)

n10 = sum(x % 10 == 0 for x in a)
n2 = sum(x % 2 == 0 and x % 5 != 0 for x in a)
n5 = sum(x % 5 == 0 and x % 2 != 0 for x in a)

count = n10 * (n - n10) + n10 * (n10 - 1) // 2 + n2 * n5

a10 = sorted([x for x in a if x % 10 == 0], reverse=True)
a2 = sorted([x for x in a if x % 2 == 0 and x % 5 != 0], reverse=True)
a5 = sorted([x for x in a if x % 5 == 0 and x % 2 != 0], reverse=True)
a0 = sorted([x for x in a if x % 2 != 0 and x % 5 != 0], reverse=True)

sums = []

if len(a10) >= 2:
    sums.append(a10[0] + a10[1])

if a10 and a2:
    sums.append(a10[0] + a2[0])

if a10 and a5:
    sums.append(a10[0] + a5[0])

if a10 and a0:
    sums.append(a10[0] + a0[0])

if a2 and a5:
    sums.append(a2[0] + a5[0])

max_sum = max(sums)

print(count, max_sum)

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

13510315 19999