Карточки
Тесты
Главная
Курсы
Подписка
17. Числовые последовательности: #297013
В файле содержится последовательность из $10,000$ целых положительных чисел. Каждое число не превышает $10,000$.
Определите и запишите в ответе сначала количество пар элементов последовательности, разность которых четна и хотя бы одно из чисел делится на $31$, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два различных элемента последовательности. Порядок элементов в паре не важен.
В этой задаче элементы пары не обязаны стоять рядом. Нужно рассмотреть любые два различных элемента последовательности, причём порядок элементов в паре не важен.
Разность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность. Значит, подходят только пары из двух чётных чисел или из двух нечётных чисел.
В файле: $5043$ чётных числа, из них $158$ делятся на $31$; $4957$ нечётных чисел, из них $161$ делится на $31$.
Сначала посчитаем подходящие пары чётных чисел. Из всех пар двух чётных вычтем те пары, в которых ни одно число не делится на $31$:
$\binom{5043}{2}-\binom{5043-158}{2}=784233$.
Аналогично для нечётных чисел:
$\binom{4957}{2}-\binom{4957-161}{2}=785036$.
Общее количество подходящих пар: $784233+785036=1569269$.
Теперь найдём максимальную сумму.
Максимальное чётное число последовательности равно $10000$.
Максимальное подходящее чётное число, делящееся на $31$, равно $9982$. Оно также встречается в файле.
Проверим: $9982=31\cdot322$.
Оба числа чётные, поэтому их разность чётна: $10000-9982=18$.
Сумма элементов: $10000+9982=19982$.
Код на Python
a = [int(x) for x in open('17-25.txt')]
count = 0
max_sum = 0
cnt_even = 0
cnt_odd = 0
cnt_even_31 = 0
cnt_odd_31 = 0
max_even = 0
max_odd = 0
max_even_31 = 0
max_odd_31 = 0
for x in a:
if x % 2 == 0:
if x % 31 == 0:
count += cnt_even
if max_even != 0:
max_sum = max(max_sum, x + max_even)
else:
count += cnt_even_31
if max_even_31 != 0:
max_sum = max(max_sum, x + max_even_31)
cnt_even += 1
max_even = max(max_even, x)
if x % 31 == 0:
cnt_even_31 += 1
max_even_31 = max(max_even_31, x)
else:
if x % 31 == 0:
count += cnt_odd
if max_odd != 0:
max_sum = max(max_sum, x + max_odd)
else:
count += cnt_odd_31
if max_odd_31 != 0:
max_sum = max(max_sum, x + max_odd_31)
cnt_odd += 1
max_odd = max(max_odd, x)
if x % 31 == 0:
cnt_odd_31 += 1
max_odd_31 = max(max_odd_31, x)
print(count, max_sum)Программа выводит:
1569269 19982
20
