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

На кольцевой автодороге с двусторонним движением находится $N$ многоэтажных жилых домов (не более одного дома на каждом километре дороги). Длина кольцевой автодороги равна $K$ км. Нулевой километр и $K$ -й километр находятся в одной точке. Жители домов ежедневно получают почту, которую доставляют роботы-почтальоны. Почта упакована в доставочные пакеты, каждый из которых вмещает не более $V$ кг посылок или писем. Каждый доставочный пакет используется для доставки почты только в один жилой дом, при этом в каждый дом может быть доставлено не более одного пакета с неполной загрузкой. Известно, что заряд аккумулятора робота-почтальона позволяет ему проходить не более $M$ км, заряд аккумулятора для возвращения робота в почтовое отделение не учитывается. Почтовое отделение открыли в одном из домов таким образом, чтобы количество доставляемых пакетов с корреспонденцией было максимальным. Почта в те дома, которые находятся на расстоянии более $M$ от почтового отделения, не доставляется. Определите необходимое количество доставочных пакетов в этом почтовом отделении.

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

В первой строке стоят числа $N,K, V$ и $M$ $(1 < N < 10000000,1 < K < 10000000,1 < V < 10000,1 < M < 10000000)$ — количество жилых домов, длина кольцевой автодороги в километрах и максимальное расстояние, на которое робот может осуществлять доставку почтовых отправлений.

В каждой из следующих $N$ строк находятся два числа: номер километра кольцевой автодороги, на котором расположен жилой дом, и вес ежедневной корреспонденции (все числа натуральные, вес писем и посылок для каждого дома не превышает 1000 кг). Данные указаны в порядке расположения домов на автодороге.

Пример входных данных:

$5$ $11$ $3$ $3$

$1$ $8$

$3$ $7$

$5$ $6$

$7$ $5$

$9$ $3$

При таких исходных данных оптимальное расположение почтового отделения – в доме с номером 3. В этом случае количество пакетов для доставки корреспонденции составит: 3 (для дома 1) + 3 (для дома 3) + 2 (для дома 5) = 8. В дома 7 и 9 почту доставить не удаётся.

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

f = open(’27b.txt’)
n, k, v, m = list(map(int, f.readline().split()))
a = [0] * k

for i in range(n):
    kilometer_num, pochta = list(map(int, f.readline().split()))
    a[kilometer_num % k] = pochta // v + (pochta % v > 0)

min_s = sum(a)
if m < (k + 1) // 2 - 1:
    c = sum(a[:m*2 + 1])
    if a[m]:
        min_s = c
    else:
        min_s = 0

    for i in range(1, k):
        c += a[(i + m * 2) % k] - a[i - 1]
        if a[(i + m) % k]:
            min_s = max(min_s, c)

print(min_s)

Ответ: 1202 70082