Задание EGEINF204C0F: Пары и тройки в числовых данных

Решение.
В файле 6685 чисел. Тройка — только три соседних элемента; произвольные сочетания из файла не рассматриваем. Соседние тройки могут иметь общие элементы, и каждая проверяется отдельно.

Сначала по всей последовательности находим M — наибольшее значение среди чисел, десятичная запись которых оканчивается на 27. Проверка окончания: abs(x) % 100 == 27. Модуль нужен только для цифр записи; сам максимум берём по исходным значениям, сохраняя знак. Из файла получаем M = 73627.

Число имеет 5 цифр тогда и только тогда, когда 10000 ≤ |x| < 100000. Знак минуса не является цифрой, а правая граница не включается. В каждой тройке считаем k — количество элементов с таким числом цифр. По условию требуется не менее одного: проверяем k >= 1.

После проверки количества цифр находим обычную сумму трёх исходных чисел S, с их знаками. Второе условие: S ≥ M. Равенство допускается. Если обе проверки пройдены, увеличиваем счётчик и обновляем наибольшую подходящую сумму. Начальное значение максимума — None, чтобы не предполагать положительность ответа.

Все начала троек имеют индексы от 0 до N − 3 включительно. Поэтому range(len(a) - 2) проверяет каждую тройку ровно один раз и не выходит за конец файла.

Программа Python; data.txt — исходный текстовый файл из архива:

with open("data.txt", encoding="utf-8-sig") as f:
    a = list(map(int, f.read().split()))
M = max(x for x in a if abs(x) % 100 == 27)
count = 0
best = None
for i in range(len(a) - 2):
    triple = a[i:i + 3]
    k = sum(10000 <= abs(x) < 100000 for x in triple)
    total = sum(triple)
    if k >= 1 and total >= M:
        count += 1
        if best is None or total > best:
            best = total
print(count, best)

Получаем 453 подходящих троек; наибольшая сумма равна 285731.

Проверка максимума. В тройке с первым элементом на позиции 418 (нумерация от 1) стоят числа 95870, 90500, 99361. Их сумма 95870 + 90500 + 99361 = 285731. Эта тройка удовлетворяет обоим условиям. Независимый проход по всем окнам подтвердил и количество, и максимальную сумму; существование одного примера не заменяет полный перебор.

Сложность двух проходов линейная по количеству чисел; внутри каждой тройки выполняется постоянное число операций.

Ответ: 453 285731.