17. Числовые последовательности: Определите количество пар последовательности, в которых сумма…
В файле содержится последовательность натуральных чисел. Её элементы могут принимать целые значения от $1$ до $100,000$ включительно. Определите количество пар последовательности, в которых сумма остатков от деления обоих элементов на $12$ равна минимальному элементу последовательности.
В ответе запишите количество найденных пар, затем минимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
Сначала найдём минимальный элемент всей последовательности. Минимальный элемент равен $8$. Теперь будем рассматривать все пары соседних элементов последовательности.
Для каждой пары чисел $x$ и $y$ найдём остатки от деления на $12$: $x\bmod12$ и $y\bmod12$.
По условию сумма этих остатков должна быть равна минимальному элементу последовательности: $x\bmod12+y\bmod12=8$.
Если это условие выполняется, увеличиваем количество подходящих пар и вычисляем сумму их элементов: $x+y$.
После перебора всей последовательности получаем $639$ подходящих пар.
Теперь среди всех подходящих пар найдём минимальную сумму. Она равна $3716$ и получается для соседних чисел $943$ и $2773$.
Проверим остатки:
$943\bmod12=7$,
$2773\bmod12=1$.
Их сумма: $7+1=8$. Значит, пара подходит.
Сумма элементов пары: $943+2773=3716$.
Код на Python
a = [int(x) for x in open('17-15-1.txt')]
m = min(a)
count = 0
min_sum = 10**20
for i in range(len(a) - 1):
x = a[i]
y = a[i + 1]
if x % 12 + y % 12 == m:
count += 1
min_sum = min(min_sum, x + y)
print(count, min_sum)
Программа выводит:
639 3716