Задача к ЕГЭ по информатике на тему «Передвижение по магистрали» №1

У медицинской компании есть N пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах, каждый из которых вмещает не более 41 штуки. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.

Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.

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

Входные данные: Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число (1 ≤ N ≤ 107)  – количество пунктов приёма биоматериалов. В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте (все числа натуральные, количество пробирок в каждом пункте не превышает 1000).

Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.

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

f = open(’27B.txt’) # Открываем нужный файл
n = int(f.readline())

points = []
all_count = 0
for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = list(map(int, f.readline().split()))
    # Считаем количество контейнеров
    cnt = (cnt // 41) + int(cnt % 41 != 0)
    all_count += cnt
    points.append([num, cnt])

# Полная стоимость относительно пункта по индексу 0
sm = 0
for i in range(n):
    # Умножаем кол-во контейнеров пункта по индексу i на расстояние до пункта по индексу 0
    sm += (points[i][0] - points[0][0]) * points[i][1]

left_count = 0
min_cost = sm
for i in range(1, n):
    # При перемещении на пункт вправее к сумме контейнеров прошлых пункта
    # добавляется контейнеры пункта points[i - 1]
    left_count += points[i - 1][1]
    # Считаем изменение расстояния
    r = points[i][0] - points[i - 1][0]
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    sm = sm + left_count * r - (all_count - left_count) * r
    min_cost = min(min_cost, sm)

print(min_cost)

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