Задание №17 — Обработка числовой информации
В файле содержится последовательность натуральных чисел, каждое из которых не превышает 100 000. Определите количество троек элементов последовательности, в которых ровно два из трёх элементов являются трёхзначными числами, а сумма элементов тройки не больше максимального элемента последовательности, оканчивающегося на 13.
Гарантируется, что в последовательности есть хотя бы одно число, оканчивающееся на 13. В ответе запишите количество найденных троек чисел, затем максимальную из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.
Правильный ответ
959 97471
Пояснение
Решение:
Задача решается одним проходом по файлу, но сначала нужно вычислить «планку» — максимальный элемент последовательности, оканчивающийся на 13. Число оканчивается на 13 тогда и только тогда, когда остаток от его деления на 100 равен 13. Для данного файла эта планка равна 98413.
Дальше перебираем все тройки идущих подряд элементов (то есть окна вида ) и проверяем два условия: ровно два числа тройки трёхзначные, то есть лежат в диапазоне от 100 до 999, и сумма всех трёх чисел не превосходит найденной планки. Считаем такие тройки и параллельно запоминаем наибольшую из их сумм.
Подходящих троек оказывается 959, а наибольшая сумма среди них равна 97471.
a = [int(line) for line in open('17.txt')]
limit = max(x for x in a if x % 100 == 13) # 98413
count = 0
best = 0
for i in range(len(a) - 2):
t = a[i:i + 3]
if sum(100 <= x <= 999 for x in t) == 2 and sum(t) <= limit:
count += 1
best = max(best, sum(t))
print(count, best) # 959 97471
Ответ: 959 97471