Задача к ЕГЭ по информатике на тему «Мусорки, кольцевая дорога» №3

На каждом километре односторонней кольцевой автодороги расположены дачные участки. Администрация дачного поселения планирует построить теплицы и выращивать в них сельсхоз. продукцию на одном из участков. При этом рассаду для посева разрешается перевозить не менее чем на K километров, и не более чем на M километров. Известен необходимый суточный объём рассады, которую необходимо доставить грузовиком для определённого дачного участка. Гарантируется, что объём рассады не превышает грузоподъёмность грузовика. Стоимость доставки равна сумме расстояния от фабрики до участка и объёма необходимой рассады. Теплицы расположили на таком участке, что при этом общая стоимость доставок удобрений на все участки, находящиеся на удалении от K до M километров, минимальна.

Определите минимальную общую стоимость доставки удобрений из теплиц.

Входные данные

Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит три числа, разделённые пробелами: N (1 ≤ N ≤ 10000000)  – количество дачных участков, K и M – минимальное и максимальное расстояние для перевозки (1 ≤ K ≤ M  ≤ N − 1)  . В каждой из следующих N строк находится объём рассады (не превышает 5000). Числа указаны в порядке расположения домов на кольцевой автодороге, начиная с первого километра.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

#Решение А
f = open(’27-10A.txt’)
n,k,m = map(int,f.readline().split())
a = [int(i) for i in f]*2
mn = 10**20
for i in range(n):
    s = 0
    for j in range(2 * n):
        if k <= (j - i) <= m:
            s += (j - i) + a[j]
    mn = min(mn,s)
print(mn)

#Решение B
f = open(’27-10B.txt’)
n,k,m = map(int,f.readline().split())
a = [int(i) for i in f]*2
r = sum(j for j in range(k,m+1))
s = mn = sum(a[k:m+1]) + r
for i in range(1,n):
    s = s - a[i+k-1] + a[i+m]
    mn = min(mn,s)
print(mn)

Ответ: 6404 56775869
Оцените статью
Я решу все!