17. Числовые последовательности: Определите количество пар последовательности, в которых остаток от…
В файле содержится последовательность натуральных чисел. Её элементы могут принимать целые значения от $1$ до $100,000$ включительно. Определите количество пар последовательности, в которых остаток от деления хотя бы одного из элементов на $16$ равен минимальному элементу последовательности.
В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
Сначала найдём минимальный элемент всей последовательности. Минимальный элемент равен $8$. Теперь будем рассматривать все пары соседних элементов $x$ и $y$.
По условию пара подходит, если остаток от деления хотя бы одного элемента на $16$ равен $8$:$x\bmod16=8$ или $y\bmod16=8$.
Для каждой подходящей пары увеличиваем счётчик и вычисляем сумму: $x+y$.
После перебора всей последовательности получаем $1214$ подходящих пар.
Максимальная сумма равна $176024$. Она получается для соседних чисел $87456$ и $88568$.
Проверим остатки:
$87456\bmod16=0$,
$88568\bmod16=8$.
Хотя бы один остаток равен минимальному элементу последовательности.
Сумма пары: $87456+88568=176024$.
Код на Python
a = [int(x) for x in open('17-19.txt')]
m = min(a)
count = 0
max_sum = 0
for i in range(len(a) - 1):
x = a[i]
y = a[i + 1]
if x % 16 == m or y % 16 == m:
count += 1
max_sum = max(max_sum, x + y)
print(count, max_sum)
Программа выводит:
1214 176024