Метеорологическая станция ведёт наблюдение за количеством выпавших осадков. Показания записываются каждую минуту в течение N минут.
Определяется пара измерений, между которыми прошло не менее K минут. Найдите максимальную сумму показаний среди таких пар.
Даны два входных файла (A и B), каждый из которых в первой строке содержит число N — количество измерений, во второй строке K — минимальное количество минут между искомыми измерениями. В каждой из следующих N строк находится число: количество выпавших осадков.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем — для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ:
Решение. Приведём решение на языке Python.
f = open('27А.txt')
N = int(f.readline())
K = int(f.readline())
a = [int(x) for x in f]
m=0
maxi=0
for i in range(K,N):#перебираем числа начиная с К, так как между измерениями прошло менее K минут
m=max(m, a[i-K])#выбираем максимальное измерение на растоянии не менее К
maxi = max(maxi, a[i] + m)#определяем максимальную сумму измерений
print(maxi)
В результате работы данного алгоритма при вводе данных из файла A ответ — 174902, из файла B — 3094684.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение Юрия Красильникова на языке Python.
PDF-версии: 