Задача 17 ЕГЭ по информатике: как решить на питоне в пять строчек

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне

 

В задаче 17 дается файл, в котором записана последовательность целых чисел. Требуется некоторым образом обработать эту последовательность. Чаще всего нужно найти количество пар или троек соседних чисел, причем эти пары или тройки должны удовлетворять некоторому условию. 

Вообще говоря, задача 17 не слишком сложная. Я, однако, хочу рассмотреть способ написания более короткого программного кода.

Рассмотрим одну из таких задач. В ней дается последовательность чисел, которые находятся в диапазоне от -1000000 до 1000000. Требуется найти в этой последовательности количество троек (т.е. трех идущих подряд чисел), в которых 1) пятизначными числами являются только два из трех и 2) сумма чисел тройки не больше максимального элемента последовательности, оканчивающегося на 29. Нужно напечатать количество таких троек и максимальную из сумм элементов этих троек. (Эта задача предлагалась на ЕГЭ по информатике в 2023 г.)

Прежде всего перепишем числа из последовательности в список.

Создание списка из чисел в файле

Самый простой способ: открываем файл, создаем пустой список, читаем файл строчка за строчкой, преобразуем каждую строчку в целое число и добавляем это число в список. Это выглядит примерно так:

f=open('17.txt')
a=[]
for s in f:
    a.append(int(s))

Однако эти четыре строчки можно заменить одной:

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

Короче и достаточно понятно, не так ли?

 

Поиск максимального числа, оканчивающегося на 29

Как определить, что число оканчивается на 29? Очень просто: найти остаток от деления этого числа на 100. Если он равен 29, то это число нам подходит.

Но тут есть ловушка. Для положительных чисел это верно, но для отрицательных - нет. Проверьте сами: выполните программу

print(129%100) # ответ: 29

А теперь - программу 

print(abs(-129)%100) # ответ: 71

Неожиданно, правда?  Дело в том, что питон для отрицательных чисел в качестве остатка от деления берет разность между данным числом и максимальным числом, не превосходящим заданное и кратным 100. (К слову, в С++ и паскале остаток от деления -129 на 100 равен -29).

Выход простой: применить функцию abs, которая возвращает модуль (абсолютную величину) числа. Проверьте:

print(abs(-129)%100) # ответ: 29

 

Разумеется, если в условии сказано, что в файле содержатся только натуральные числа, то функцию abs можно не применять. (Хотя, как известно, настоящий программист, переходя улицу, всегда посмотрит сначала налево, а потом направо - даже если это улица с односторонним движением.)

Обычно поиск максимального числа, оканчивающегося на 29, записывают примерно так: 

max29=-1000001
for x in a:
if abs(x)%100==29:
max29=max(max29,x)

Но опять-таки это можно записать короче:

max29=max([x for x in a if abs(x)%100==29])

Как это работает?

Конструкция  [x for x in a if abs(x)%100==29] создает список, состоящий только из тех элементов списка a, которые удовлетворяют условию abs(x)%100==29. А функция max возвращает максимальный элемент этого списка.

Подсчет количества троек и поиск максимальной суммы

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

Обычно записывают следующий цикл:

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

Элементы тройки - это числв a[i], a[i+1] и a[i+2].

Проверку числа x на пятизначность можно выполнять или как  10000<=abs(x)<100000, или как len(str(abs(x)))==5.

Код для выполнения этой задачи обычно выглядит примерно так:

k=0
ms=-2000000
for i in range(len(a)-2):
k5=0
for j in range(3):
if 10000<=abs(a[i+j])<100000:
k5+=1
if k5==2 and a[i]+a[i+1]+a[i+2]<=max29:
k+=1
ms=max(ms,a[i]+a[i+1]+a[i+2])

 

В переменной k5 мы подсчитываем количество пятизначных чисел в текущей тройке.

Этот код можно немного сократить.

Логические величины в питоне можно использовать в арифметических операциях, при этом True трактуется как 1, а False - как 0. Поэтому подсчет количества пятизначных чисел можно реализовать так:

sum([10000<=abs(x)<100000 for x in a[i:i+3]])

Использовав этот прием, можно сделать код несколько короче:

k=0
ms=-2000000
for i in range(len(a)-2):
if sum([10000<=abs(x)<100000 for x in a[i:i+3]])==2 and a[i]+a[i+1]+a[i+2]<=max29:
k+=1
ms=max(ms,a[i]+a[i+1]+a[i+2])

 

Но мы пойдём другим путем: создадим список b, элементы которого - это тройки последовательных чисел из нашего списка а. Это опять-таки можно сделать в одну строку:

b=[a[i:i+3] for i in range(len(a)-2)]

Таким образом, список b - это [ [a[0],a[1],a[2]], [a[1], a[2],a[3]],...]

А теперь создадим список c, в который войдут суммы троек, но не всех, а только отвечающих условиям задачи. Это - ещё одна строка кода:

c=[sum(x) for x in b if sum([10000<=abs(n)<100000 for n in x])==2 and sum(x)<=max29]

Всё, что осталось сделать - это отпечатать количество элементов списка c и его максимальный элемент.

Приведем программу полностью:

a=[int(s) for s in open('17.txt')]
max29=max([x for x in a if abs(x)%100==29])
b=[a[i:i+3] for i in range(len(a)-2)]
c=[sum(x) for x in b if sum([10000<=abs(n)<100000 for n in x])==2 and sum(x)<=max29]
print(len(c),max(c))

Пять строчек - и задача решена.

Для сравнения приведем "более классический" вариант решения (в нём 19 строчек, почти вчетверо больше, правда, строчки короткие):

f=open('17.txt')
a=[]
for s in f:
a.append(int(s))
max29=-1000001
for x in a:
if abs(x)%100==29:
max29=max(max29,x)
k=0
ms=-2000000
for i in range(len(a)-2):
k5=0
for j in range(3):
if 10000<=abs(a[i+j])<100000:
k5+=1
if k5==2 and a[i]+a[i+1]+a[i+2]<=max29:
k+=1
ms=max(ms,a[i]+a[i+1]+a[i+2])
print(k,ms)

С вариантами решения задачи на паскале сравнивать не буду: там тексты вдвое длиннее...

(Опасаюсь, что когда составители заданий для ЕГЭ поймут, что 17-я задача может решаться столь коротко, то они придумают что-то более мудрёное...)

(c) Ю.Д.Красильников, 2024 г.