Задание 27. Информатика. ЕГЭ 2024. Крылов-1

По каналу связи ежедневно раз в день в течение \(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\) не следует использовать переборный алгоритм, вычисляющий сумму для всех всевозможных вариантов, поскольку по такому алгоритму программа будет выполняться слишком долго.

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)