Задание 27. Информатика. ЕГЭ 2024. Крылов-1
- Просмотры: 14
- Изменено: 7 сентября 2024
По каналу связи ежедневно раз в день в течение \(N\) дней (\(N\) — натуральное число) передаётся последовательность натуральных чисел — сумма выручки в некотором отделении банка за день.
Определите три таких переданных числа, чтобы между моментами передачи любых из двух из них прошло не менее \(K\) дней, а сумма этих трёх чисел была минимально возможной. Запишите в ответе найденную сумму.
Входные данные
Даны два входных файла (файл \(A\) и файл \(B\)), каждый из которых в первой строке содержит натуральное число \(K\) — минимальное количество дней, которое должно пройти между моментами передачи сумм выручки, а во второй — количество переданных значений \(N\) ( \(1 \leqslant N \leqslant 10~000~000\), \(N>K\)). В каждой из следующих \(N\) строк находится одно натуральное число, не превышающее \(10~000~000\), которое обозначает сумму выручки в отделении банка за соответствующий день.
Запишите в ответе два числа: сначала значение искомой величины для файла \(A\), затем — для файла \(B\).
Типовой пример организации данных во входном файле
\(2\)
\(6\)
\(15\)
\(26\)
\(30\)
\(23\)
\(22\)
\(20\)
При таких исходных данных искомая величина равна \(65\) — это сумма значений выручки, полученной в первый, третий и шестой дни.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение: для обработки файла \(B\) не следует использовать переборный алгоритм, вычисляющий сумму для всех всевозможных вариантов, поскольку по такому алгоритму программа будет выполняться слишком долго.
Решение:
Python
Переборный алгоритм
f = open('27v01_A.txt')
K = int(f.readline())
N = int(f.readline())
a = [int(x) for x in f]
min_sum = 10 * 100
for i in range(N - 2 * K):
for j in range(i + K, N - K):
for k in range(i + 2 * K, N):
min_sum = min(min_sum, a[i] + a[j] + a[k])
print(min_sum)
Эффективный алгоритм
flist = ('27v01_A.txt', '27v01_B.txt')
for fname in flist:
f = open(fname)
K = int(f.readline())
N = int(f.readline())
a = [int(x) for x in f]
min_left = [10 * 20] * N
min_right = [10 * 20] * N
min_left[0] = a[0]
for i in range(1, N):
min_left[i] = min(min_left[i - 1], a[i])
min_right[-1] = a[-1]
for i in range(N - 2, -1, -1):
min_right[i] = min(min_right[i + 1], a[i])
min_sum = 10 ** 20
for i in range(K, N - K):
min_sum = min(min_sum, min_left[i - K] + a[i] + min_right[i + K])
print(min_sum)
Эффективный однопроходный алгоритм
flist=('27v01_A.txt', '27v01_B.txt')
for fname in flist:
f = open(fname)
K = int(f.readline())
N = int(f.readline())
a = [int(x) for x in f]
min1, min2, min3 = 10**10, 10**10, 10**10
for i in range(N - 2*K):
min1 = min(min1, a[i])
min2 = min(min2, min1 + a[i + k])
min3 = min(min3, min2 + a[i + 2*k])
print(min3)
Ответ: \(987 \,\, 11408812\)