Карточки
Тесты
Главная
Курсы
Подписка
17. Числовые последовательности: #296996
В файле содержится последовательность из $10,000$ натуральных чисел. Каждое число не превышает $10,000$.
Определите и запишите в ответе сначала количество пар элементов последовательности, у которых различные остатки от деления на $d=160$ и хотя бы одно из чисел делится на $p=7$, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два различных элемента последовательности. Порядок элементов в паре не важен.
В этой задаче элементы пары не обязаны стоять рядом. Нужно рассмотреть любые два различных элемента последовательности, причём порядок элементов в паре не важен.
Будем просматривать последовательность слева направо. Для текущего числа $x$ будем составлять пары только с уже просмотренными числами. Тогда каждая пара будет учтена ровно один раз.
Для каждого остатка от деления на $160$ будем хранить количество уже просмотренных чисел с таким остатком.
Также отдельно будем хранить количество среди них чисел, которые делятся на $7$.
Пусть $r=x\bmod160$.
Если текущее число $x$ делится на $7$, то вторым элементом может быть любое уже просмотренное число, у которого остаток от деления на $160$ не равен $r$.
Если же $x$ не делится на $7$, то второй элемент обязательно должен делиться на $7$ и иметь другой остаток от деления на $160$.
Для поиска максимальной суммы аналогично запоминаем максимальные элементы для каждого остатка, а отдельно — максимальные элементы, кратные $7$.
После обработки всего файла получаем $12,749,665$ подходящих пар.
Максимальная сумма равна $19,989$. Она получается для элементов $9989$ и $10000$. Оба числа присутствуют в файле.
Проверим делимость: $9989=7\cdot1427$, значит, один из элементов делится на $7$.
Остатки от деления на $160$:
$9989\bmod160=69$,
$10000\bmod160=80$.
Остатки различны. Сумма элементов: $9989+10000=19989$.
Код на Python
a = [int(x) for x in open('17-24.txt')]
cnt = [0] * 160
cnt7 = [0] * 160
max_all = [-1] * 160
max_7 = [-1] * 160
seen = 0
seen7 = 0
count = 0
max_sum = 0
for x in a:
r = x % 160
if x % 7 == 0:
count += seen - cnt[r]
best = max(max_all[j] for j in range(160) if j != r)
else:
count += seen7 - cnt7[r]
best = max(max_7[j] for j in range(160) if j != r)
if best != -1:
max_sum = max(max_sum, x + best)
seen += 1
cnt[r] += 1
max_all[r] = max(max_all[r], x)
if x % 7 == 0:
seen7 += 1
cnt7[r] += 1
max_7[r] = max(max_7[r], x)
print(count, max_sum)Программа выводит:
12749665 19989
20
