17. Числовые последовательности: Определите количество троек элементов последовательности, в…
В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от $-100,000$ до $100,000$ включительно. Определите количество троек элементов последовательности, в которых не более двух из трёх элементов являются четырёхзначными числами, а сумма элементов тройки не больше максимального элемента последовательности, оканчивающегося на $25$.
В ответе запишите количество найденных троек чисел, затем максимальную из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.
В первой строке файла записано количество элементов последовательности — $6678$, поэтому сами элементы начинаются со второй строки. Сначала найдём максимальный элемент последовательности, оканчивающийся на $25$.
Для проверки окончания числа на $25$ используем условие: $|x|\bmod100=25$.
Максимальный такой элемент равен $84725$. Теперь будем рассматривать все тройки подряд идущих элементов.
Число является четырёхзначным, если его абсолютное значение находится в диапазоне $1000\leq|x|\leq9999$.
По условию в тройке должно быть не более двух четырёхзначных чисел. Значит, количество четырёхзначных элементов в каждой тройке должно быть меньше или равно $2$.
Кроме того, сумма элементов тройки должна быть не больше $84725$: $x+y+z\leq84725$.
Если оба условия выполняются, увеличиваем количество найденных троек и запоминаем их сумму.
После перебора всей последовательности получаем $6314$ подходящих троек.
Максимальная сумма среди них равна $84523$. Она получается для тройки $-682,\ 85871,\ -666$.
В этой тройке нет четырёхзначных чисел, поэтому первое условие выполняется.
Проверим сумму: $-682+85871-666=84523$.
Также $84523\leq84725$, следовательно, эта тройка подходит.
Код на Python
f = open('17-14.txt')
n = int(f.readline())
a = [int(x) for x in f]
m = max(x for x in a if abs(x) % 100 == 25)
count = 0
max_sum = -10**20
for i in range(len(a) - 2):
x = a[i]
y = a[i + 1]
z = a[i + 2]
k = sum(1000 <= abs(t) <= 9999 for t in (x, y, z))
s = x + y + z
if k <= 2 and s <= m:
count += 1
max_sum = max(max_sum, s)
print(count, max_sum)
Программа выводит:
6314 84523