Тема 27. Программирование
27.01 Передвижение по магистрали
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела программирование
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#61643

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

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

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

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

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

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

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

Типовой пример организации данных во входном файле

6

1 100

2 200

5 4

7 3

8 2

10 190

При таких исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит:1 ⋅2+ 3⋅1 + 5⋅1+ 6⋅1 + 8⋅2  .

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Вложения к задаче
Показать ответ и решение

Решение А

f = open(’27A__1udcp.txt’)
n = int(f.readline())
a = []
for i in range(n):
    km, prob = map(int,f.readline().split())#считываем количество километров и количество пробирок
    count_conteiner = prob//26 if prob % 26 == 0 else prob//26 + 1 #выделяем количество контейнеров,
    # если количество пробирок не делится нацело на 26, то берем один контейнер дополнительно
    a += [[km,count_conteiner]]#добавляем эти данные в список

mn = float(’inf’)
for i in range(n):# i индекс - место лаборатории
    s = 0
    for j in range(n):# j индекс - место пункта
        s += abs(a[i][0]-a[j][0])*a[j][1]#расстояние считается как произведение расстояния между пунктами на количество пробирок в пункте
    mn = min(mn,s)
print(mn)

Решение Б

f = open(’27B__1udcq.txt’)
n = int(f.readline())
a = []
sm = 0#суммарное кол-во контейнеров
for i in range(n):
    km, prob = map(int,f.readline().split())#считываем количество километров и количество пробирок
    count_conteiner = prob//26 if prob % 26 == 0 else prob//26 + 1 #выделяем количество контейнеров,
    # если количество пробирок не делится нацело на 26, то берем один контейнер дополнительно
    sm += count_conteiner
    a += [[km,count_conteiner]]#добавляем эти данные в список

s = 0
for i in range(n):# в данном цикле высчитывается стоимость для лаборатории, котора стоит на 0 индексе
    s += (a[i][0]-a[0][0]) * a[i][1]
mn = s
expsv = 0# число контейнеров, для которых стоимость вырастет

for i in range(1,n):
    expsv += a[i-1][1]#высчитываем кол-во контейнеров, для которых стоимость вырастет при смене места лаборатории
    r = a[i][0] - a[i-1][0]# разность в км между двумя соседними пунктами
    s = s + r*expsv - r*(sm - expsv)# формируем стоимость для лаборатории стоящей, на i-ом индексе.
    # На r*expsv станет дороже стоимость, поскольку относительно магистрали мы сдвинули лабораторию правее и всё, что было левее - стало дороже,
    # но всё, что было правее лаборатории стало дешевле на r*(sm - expsv)
    mn = min(mn,s)
print(mn)

Ответ: 21059 2956646501958

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!