Задание 27. Программирование. Оптимизация по времени и памяти. ЕГЭ 2026 по информатике
Средний процент выполнения: 14.3%
Ответом к заданию 27 по информатике может быть развернутый ответ (полная запись решения с обоснованием выполненных действий).
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
Имеется набор данных, состоящий из положительных целых чисел, все числа не превышают 10000. Количество чисел известно, но может быть очень велико. Необходимо найти наибольшую сумму пары чисел, которая кратна 74. Под парой подразумеваются два числа, расположенных на разных местах в наборе, порядок в паре неважен. Программа должна напечатать одно число - наибольшую сумму чисел, соответствующих условиям задачи. Если такую сумму получить невозможно, вывести -1.
Описание входных и выходных данных
Даны два входных файла, каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 10000000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.
Пример входных данных:
4
50
410
108
98
Пример выходных данных для приведённого выше примера входных данных:
518
Решение
file = open("27_new_5.txt", "r")
size = int(file.readline())
arr = [0] * 74
max0_1, max0_2, max37_1, max37_2 = (0, 0, 0, 0)
for i in range(size):
val = int(file.readline())
if val % 74 == 0:
if val > max0_1:
max0_2 = max0_1
max0_1 = val
elif val > max0_2:
max0_2 = val
elif val % 74 == 37:
if val > max37_1:
max37_2 = max37_1
max37_1 = val
elif val > max37_2:
max37_2 = val
else:
arr[val % 74] = max(arr[val % 74], val)
maxSum = -1
if (max0_1 != 0) and (max0_2 != 0):
maxSum = max(max0_1 + max0_2, maxSum)
if (max37_1 != 0) and (max37_2 != 0):
maxSum = max(max37_1 + max37_2, maxSum)
for i in range(1, 37):
if (arr[i] != 0) and (arr[74 - i] != 0):
maxSum = max(maxSum, arr[i] + arr[74 - i])
print(maxSum)
file.close()
Задача 2
Дана последовательность целых положительных чисел не превышающих 10 000 000. Рассматриваются все пары последовательности, разность которых чётна, и в этих парах, есть число, которое делится на 17. Порядок элементов в паре неважен. Нужно для всех найденных пар вывести максимальную сумму элементов пары. Если подходящих пар в последовательности нет, нужно вывести -1.
Входные данные:
В первой строке записано число N общее количество элементов последовательности. Далее идёт N элементов.
Решение
f = open('27_B_dosrok.txt', 'r')
n = int(f.readline())
max_sum = 0
max_prev_17 = 0
max_prev = 0
first = int(f.readline())
for i in range(1, n):
second = int(f.readline())
if first % 17 == 0:
max_prev_17 = max(max_prev_17, first)
max_prev = max(max_prev, first)
if second % 17 == 0 and (max_prev - second) % 2 == 0:
max_sum = max(max_sum, max_prev + second)
else:
if (max_prev_17 - second) % 2 == 0:
max_sum = max(max_sum, max_prev_17 + second)
first = second
print(max_sum)
Задача 3
Тестовая
На кольцевой дороге с двусторонним движением установлены магазины для продажи яблок. Все магазины находятся на расстоянии 1 километра друг от друга. Специальные роботы доставщики развозят яблоки со склада по этим магазинам. Длина кольцевой дороги равна N километров. Нулевой километр и N-й километр автодороги находятся в одной точке. Известно количество килограмм яблок, которое необходимо ежедневно доставлять в каждый из магазинов. Для каждого пункта яблоки возит отдельный робот доставщик. Стоимость доставки яблок вычисляется как произведение количества яблок (в килограммах) на расстояние от склада до магазина. Склад открыли в одном из магазинов таким образом, чтобы общая стоимость доставки яблок во все магазины была минимальной.
Определите минимальные расходы на доставку яблок в магазины.
Входные данные
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (1 ≤ N ≤ 10 000 000) – количество магазинов на кольцевой дороге. В каждой из следующих N строк находится число – количество килограмм яблок, необходимых для доставки в магазин (все числа натуральные, количество килограмм не превышает 1000). Числа указаны в порядке расположения магазинов на дороге, начиная с первого километра.
В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.
Типовой пример организации данных во входном файле
6 8 20 5 13 7 19
При таких исходных данных, если магазины установлены на каждом километре дороги, необходимо открыть склад в пункте 6. В этом случае сумма затрат на доставку составит:
1 · 7 + 0 · 19 + 1 · 8 + 2 · 20 + 3 · 5 + 2 · 13.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Решение
Для решения этого номера составим программу на языке Python
f = open('27_B.txt', 'r')
n = int(f.readline().strip())
x = [int(line) for line in f]
right = 0
left = x[0]
sum_all = 0
for i in range(1, n // 2):
sum_all += i * x[i] + i * x[-i]
right += x[i]
left += x[-i]
sum_all += (n // 2) * x[n // 2]
right += x[n // 2]
min_sum = sum_all
for i in range(1, n):
sum_all = sum_all - right + left
right = right + x[(n // 2 + i) % n] - x[i]
left = left + x[i] - x[(n // 2 + i) % n]
min_sum = min(min_sum, sum_all)
print(min_sum)
Задача 4
Дан файл, состоящий из пар положительных целых чисел. Напишите программу, которая из каждой пары выбирает ровно одно число так, что сумма всех выбранных чисел не делится на 3 и при этом максимально возможна. Гарантируется, что искомую сумму получить можно.
Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Дан входной файл, каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000. Пример организации исходных данных во входном файле:
6 1 3 5 12 6 9 5 4 3 3 1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите одно число: искомую сумму для файла
Решение
f = open('27-B.txt', 'r') # открываем файл для чтения
n = int(f.readline()) # считываем общее количество
max_s = 0 # обнуляем максимальную сумму
min_r = float('inf')
for i in range(n): # запускаем цикл для считывания всех наших пар
x, y = map(int, f.readline().strip().split()) # считываем пару и сохраняем элементы в переменные x и y
max_s = max_s + max(x, y) # в предполагаемую максимальную сумму сохраняем максимальный элемент из пары
if abs(x - y) % 3 != 0: # если разноcть чисел не делится на 3
min_r = min(min_r, abs(x - y)) # то пытаемся сохранить её как минимальную
if max_s % 3 == 0: # если общая сумма кратна 3
max_s -= min_r # то вычитаем из неё минимальную разность
print(max_s) # выводим ответ
Задача 5
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 37.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000).
В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 37.
Пример входных данных:
7 74 2 3 5 4 1 37
Решение
f = open('27_2019_B.txt', 'r') # Открываем файл для чтения
n = int(f.readline().strip()) # считываем общее количество чисел в файле
n_37 = 0 # переменная отвечающая за количество чисел делящиеся на 37
a = [] # список для хранения элементов в промежутке
k = 0 # для подсчёта количества
for i in range(4): # считываем первые 4 элемента и сохраняем их в список
a.append(int(f.readline().strip())) # считываем число и сохраняем его в нашем списке-промежутке
for i in range(4, n): # запускаем цикл для проверки всех оставшихся чисел
if a[0] % 37 == 0: # проверяем делится ли самый первый (нулевой) элемент в нашем промежутке на 37
n_37 = n_37 + 1 # если делится, то увеличиваем количество делящихся на 37 на 1
x = int(f.readline().strip()) # считываем новый элемент. Он как раз находится на расстоянии 4 от нашего элемента в списке
if x % 37 == 0: # если этот элемент делится на 37
k = k + i - 4 + 1 # то мы подсчитываем количество элементов как все элементы до этой позиции, т.к. счёт начинается с 0, то добавим 1
else:
k = k + n_37 # а если не делится на 37, то он образует произведение со всеми элементами кратными 37
a.pop(0) # уберём крайний левый элемент из промежутка, он нам больше не нужен
a.append(x) # и добавим в него новый элемент, чтобы сохранять промежуток в 4
print(k) # выводим это количество
Ответ для файла А: 93
Ответ для файла В: 2797842
Задача 6
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 39.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 39.
Пример входных данных:
4 2 6 13 39
Пример выходных данных для приведённого выше примера входных данных: 4
Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·13, 2·39, 6·13, 6·39, 13·39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 39 делятся 3 произведения (2·39=78; 6·13=78; 6·39=234; 13·39=507).
Решение
f = open('27_2018_C.txt', 'r') # Открываем файл для чтения
n = int(f.readline().strip()) # считываем общее количество чисел в файле
n_39 = 0 # переменная отвечающая за количество чисел делящиеся на 39
n_3 = 0 # количество чисел делящихся на 3, но не 13
n_13 = 0 # количество чисел, делящихся на 13, но не на 3
for i in range(n): # запускаем цикл, чтобы считывать числа из файла и проверять их
x = int(f.readline().strip()) # считываем одно число
if x % 39 == 0: # если оно делится на 39
n_39 += 1 # то увеличиваем количество чисел, делящихся на 39
elif x % 3 == 0: # иначе, если число не делится на 39, то оно может делиться на 3
n_3 += 1 # увеличиваем количество чисел, делящихся на 3, но не на 13
elif x % 13 == 0: #иначе, если число делится на 13
n_13 += 1 # то увеличиваем количество чисел, делящихся на 13
k = n_3 * n_13 + n_39 * (n_39 - 1) // 2 + n_39 * (n - n_39) # вычисляем общее количество пар
print(k) # выводим это количество
Ответ на файл А: 180
Ответ на файл В: 4038533933532
Задача 7
У магазина компании есть N пунктов приёма товаров. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество товара, которое ежедневно принимают в каждом из пунктов. Товар перевозят в специальных транспортировочных контейнерах вместимостью не более 24 упаковок. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в центральном магазине.
Стоимость перевозки товара равна произведению расстояния от пункта до центрального магазина на количество контейнеров с товаром. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в центральный магазин. Центральный магазин расположили в одном из пунктов приёма товара таким образом, что общая стоимость доставки из всех пунктов минимальна. Определите минимальную общую стоимость доставки товара из всех пунктов приёма в центральный магазин.
Решение
from math import ceil
f = open('27_B.txt', 'r')
n = int(f.readline())
x = []
for line in f:
r, p = map(int, line.split())
x.append([r, ceil(p / 24)])
min_sum = 0
right = 0
for i in range(1, n):
min_sum += x[i][1] * (x[i][0] - x[0][0])
right += x[i][1]
left = x[0][1]
cur_sum = min_sum
for i in range(1, n):
cur_sum += (x[i][0] - x[i - 1][0]) * (left - right)
right -= x[i][1]
left += x[i][1]
min_sum = min(min_sum, cur_sum)
print(min_sum)
Ответ для файла А: 70476
Ответ для файла B: 7794224196663
Рекомендуемые курсы подготовки
- Узнаешь всё про кодирование: что это такое и как происходит
- Познакомишься с Условием Фано: как оно примняется и почему важно
- Научишься считать колиечтсво информации и сколько под неё нужно выделить памяти
на бесплатном курсе Турбо ЕГЭ
