17. Числовые последовательности: Определите количество пар последовательности, в которых сумма…
В файле содержится последовательность натуральных чисел. Её элементы могут принимать целые значения от $1$ до $100,000$ включительно. Определите количество пар последовательности, в которых сумма остатков от деления обоих элементов на $18$ равна минимальному элементу последовательности.
В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
Сначала найдём минимальный элемент всей последовательности. Минимальный элемент равен $8$. Теперь будем рассматривать все пары соседних элементов последовательности.
Для каждой пары чисел $x$ и $y$ найдём остатки от деления обоих элементов на $18$: $x\bmod18$ и $y\bmod18$.
По условию пара подходит, если сумма этих остатков равна минимальному элементу последовательности, то есть: $x\bmod18+y\bmod18=8$.
Если условие выполняется, увеличиваем количество найденных пар и вычисляем сумму элементов пары: $x+y$.
После перебора всей последовательности получаем $285$ подходящих пар.
Максимальная сумма элементов такой пары равна $166436$. Она получается для соседних чисел $86120$ и $80316$.
Проверим условие:
$86120\bmod18=8$,
$80316\bmod18=0$,
$8+0=8$.
Сумма элементов пары: $86120+80316=166436$.
Код на Python
a = [int(x) for x in open('17-11.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 % 18 + y % 18 == m:
count += 1
max_sum = max(max_sum, x + y)
print(count, max_sum)
Программа выводит:
285 166436