Списки и обработка последовательностей

Если посмотреть все задания линии 17 в банке ФИПИ подряд, обнаруживается удивительная вещь: формулировка у них одна, и меняется в ней ровно одно придаточное. Вот реальные концовки условий:

— «определите количество пар последовательности, оба элемента которых — нечётные числа, и максимальную из сумм элементов таких пар»; — «…сумма элементов которых делится на 9 без остатка…»; — «…модуль разности элементов которых делится на 13 без остатка…»; — «…ровно один элемент которых — чётное число…»; — «…оба элемента которых — четырёхзначные числа…»; — «…оба элемента которых больше среднего арифметического всех элементов последовательности…».

И всегда одно и то же уточнение: «Под парой подразумеваются два идущих подряд элемента последовательности».

Значит, учить надо не пятьдесят решений, а один шаблон и способ вставить в него условие. Ответ тоже всегда одинаков по форме: сначала количество подходящих пар, потом наибольшая из их сумм.

Отдельно стоит вариант со средним арифметическим: он единственный, где одного прохода не хватает, и разобран ниже отдельно.

Программа состоит из четырёх частей, и три из них не меняются никогда.

Чтение файла. a = [int(x) for x in open('17.txt')]. В файле числа записаны по одному в строке, и int сам отбрасывает перевод строки, так что strip() не нужен.

Перебор соседних пар. for i in range(len(a) - 1), внутри x, y = a[i], a[i + 1]. Граница len(a) - 1 обязательна: при range(len(a)) на последнем шаге обращение к a[i + 1] вылетит за конец списка. Пар всегда ровно на одну меньше, чем элементов.

Два накопителя. kolichestvo = 0 и maksimum = 0. Второй лучше заводить нулём, а не None: суммы в линии 17 положительные, и нуль никогда не окажется больше настоящей суммы. Если бы элементы могли быть отрицательными, надёжнее было бы maksimum = None с проверкой.

Условие. Единственная строка, которая меняется от варианта к варианту.

a = [int(x) for x in open('17.txt')]

kolichestvo = 0

maksimum = 0

for i in range(len(a) - 1):

x, y = a[i], a[i + 1]

if x % 2 == 1 and y % 2 == 1: # ← вот эта строка

kolichestvo += 1

if x + y > maksimum:

maksimum = x + y

print(kolichestvo, maksimum)

Восемь строк, из которых думать надо над одной. Выучите каркас так, чтобы он набирался механически, и всё внимание останется на условии.

Формулировка «ровно один элемент которых — чётное число» ломает больше решений, чем все остальные вместе. Соблазн написать x % 2 == 0 or y % 2 == 0 велик, но это неверно: обычное «или» в Python включающее, и пара из двух чётных чисел тоже его удовлетворит.

Правильных записей три, и все годятся.

Через неравенство логических значений. (x % 2 == 0) != (y % 2 == 0). Каждая скобка даёт True или False; они не равны ровно тогда, когда одно из чисел чётное, а другое нет.

Через счёт. [x % 2, y % 2].count(0) == 1 — среди двух остатков ровно один нулевой.

Через чётность суммы. Сумма чётного и нечётного всегда нечётна, а сумма двух одинаковых по чётности — чётна. Значит, (x + y) % 2 == 1 — самая короткая запись того же условия. Она работает только для признака чётности; для «ровно один оканчивается на 5» так сократить не выйдет, там нужен первый способ.

Проверьте себя на паре (8, 21): чётное и нечётное, «ровно один чётный» выполнено. На паре (12, 24): оба чётные, условие не выполнено. На паре (7, 9): оба нечётные, тоже не выполнено.

Вариант «оба элемента больше среднего арифметического всех элементов последовательности» устроен иначе, и в нём теряют балл чаще всего.

Причина в слове «всех». Среднее зависит от всей последовательности, включая числа, до которых цикл ещё не дошёл. Значит, считать среднее «на лету» в том же проходе, где идёт отбор, нельзя: на первых шагах оно будет посчитано по неполным данным и окажется неверным.

Правильный порядок — два прохода:

Первый проход (или просто sum(a) / len(a)) даёт среднее по всей последовательности.

Второй проход идёт по парам и сравнивает элементы с уже известным числом.

Вторая тонкость — деление. sum(a) / len(a) даёт дробное число, и это правильно: округлять среднее нельзя. Если написать sum(a) // len(a), целочисленное деление отбросит дробную часть, и элементы, попадающие между настоящим средним и округлённым, будут отнесены не в ту сторону. На средних вроде 14,4 это меняет ответ.

Та же логика работает во всех формулировках со словами «всех», «максимального», «наименьшего»: величина, вычисляемая по всей последовательности, требует отдельного прохода до начала отбора.

Шаблон опирается на то, что в файле по одному числу в строке. Так и бывает в линии 17, но проверить стоит — на это уходит пять секунд, а ошибка иначе будет искаться долго.

Откройте файл и посмотрите на первые строки. Возможны три ситуации.

По одному числу в строке — обычный случай. a = [int(x) for x in open('17.txt')] работает как есть.

Несколько чисел в строке через пробел. Тогда список строится иначе:

a = [int(x) for x in open('17.txt').read().split()]

split() без аргументов режет по любому количеству пробелов и переводов строки сразу, поэтому один этот вариант покрывает и предыдущий случай. Если сомневаетесь — пишите сразу его.

Первая строка — количество чисел. Такое встречается в линиях 26 и 27, и если её не отделить, счётчик попадёт в данные и испортит и сумму, и среднее:

f = open('17.txt')

n = int(f.readline())

a = [int(x) for x in f]

Проверить себя проще всего печатью: print(len(a), a[:5], a[-5:]). Длина должна совпадать с объявленной в условии или с числом из первой строки, а первые и последние элементы — выглядеть правдоподобно. Одна эта строчка ловит почти все ошибки чтения, и убирают её только перед записью ответа.

Непересекающиеся пары. Каждый элемент, кроме первого и последнего, входит в две пары — как правый сосед и как левый. Разбиение последовательности на пары «через одну» уменьшает ответ примерно вдвое.

Выход за границу. for i in range(len(a)) вместо len(a) - 1 даёт IndexError на последнем шаге. Ошибка заметная — программа падает, — и потому не опасная; опаснее обратная, когда пишут len(a) - 2 и теряют последнюю пару.

Включающее «или» вместо строгого выбора одного из двух. Разобрано выше: включающее «или» захватывает лишние пары.

Среднее в одном проходе. Величина, вычисляемая по всей последовательности, должна быть посчитана до начала отбора.

Максимум вместо суммы. Условие просит «максимальную из сумм элементов таких пар», а не максимальный элемент среди подходящих пар. Сравнивать надо x + y, а не x и y по отдельности.

Порядок двух чисел в ответе. Сначала количество, потом максимальная сумма. Переставленные местами числа — это ноль баллов при полностью верной программе, и случается это чаще, чем хотелось бы.

Отладка на маленьком файле. В условии всегда есть типовой пример с известным ответом. Прогоните программу на нём, сверьте — и только потом запускайте на боевом файле.

Список в Python — это последовательность с доступом по индексу с нуля; a[-1] — последний элемент, срез a[i:i+2] — пара соседних. Готовые функции len, sum, max, min, a.count(x) закрывают почти всю арифметику линии 17.

Вся линия 17 — один шаблон из восьми строк: прочитать файл списком, пройти по индексам до len(a) - 1, взять пару a[i], a[i+1], проверить условие, обновить два накопителя, напечатать их через пробел. Меняется в нём одна строка условия, и таблица выше даёт её для всех формулировок банка.

Два места требуют отдельного внимания. «Ровно один» — это исключающее «или», короче всего записываемое как нечётность суммы. «Больше среднего арифметического всех элементов» — это два прохода, причём среднее считается обычным делением, без округления.

И помните про форму ответа: два числа через пробел, сначала количество, затем максимальная из сумм.