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

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

Задача 1#88158

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

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

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

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

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

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

Вложения к задаче
Показать ответ и решение
# Файлик A
from math import ceil

f = open(’3_27A.txt’)
k = 111
n = int(f.readline())

points = []
for i in f:
    dist, cnt = map(int, i.split())
    # Чтобы контейнеров точно хватило, нужно округлять в большую сторону - ceil
    points.append([dist, ceil(cnt / k)])

costs = []
for cur_d, cur_c in points:
    # Перебираем пункты, где можем поставить лабораторию
    sm = 0
    for dist, cnt in points:
        # Для пункта увеличиваем сумму - умножаем расстояние до лаборатории на количество контейнеров
        sm += abs(dist - cur_d) * cnt
    costs.append(sm)

print(max(costs) - min(costs))


# Файлик B
from math import ceil

f = open(’3_27B.txt’)
k = 111
n = int(f.readline())

# Список, в котором индекс - расстояние от нулевой отметки до этого пункта
# элементы - количества контейнеров
# Если на какой-то отметке пункта нет, там останется 0, и этот пункт не будет
# влиять на сумму

points = [0] * 10 ** 7

# Индексы первого и последнего реального пункта
start = 10 ** 10
end = -1

                                                                                                  
                                                                                                  
for i in range(n):
    # Считываем номер пункта и количество пробирок
    num, cnt = map(int, f.readline().split())
    # Вставляем на нужную отметку кол-во контейнеров
    points[num] = ceil(cnt / k)
    # Определяем крайние пункты
    if cnt > 0:
        start = min(start, num)
        end = max(end, num)

# Удаляем нулевые пункты по краям
points = points[start: end + 1]

# Изначальная сумма для 0-го пункта
sm = 0

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

# Если мы смещаемся на пункт вправо - расстояние до всех пунктов слева увеличится на 1,
# значит общая сумма увеличится на сумму пунктов слева

# Расстояние до всех пунктов справа уменьшится на 1,
# значит общая сумма уменьшится на сумму пунктов справа

# Сумма слева, на которую увеличится общая сумма при перемещении на один пункт вправо
left = 0
# Сумма справа, на которую уменьшится общая сумма при перемещении на один пункт вправо
right = sum(points)

current_cost = sm
# Список сумм для каждого пункта
costs = [sm]

for i in range(1, len(points)):
    # При перемещении на 1 пункт вправо из правой суммы исчезает самый перый элемент,
    # а к левой этот элемент прибавляется
    left += points[i - 1]
    right -= points[i - 1]
    # Рассчёт новой суммы, после увеличения суммы левой суммой и уменьшения правой суммой
    current_cost = current_cost + left - right
    if points[i] > 0:
        costs.append(current_cost)

print(max(costs) - min(costs))
                                                                                                  
                                                                                                  

Ответ: 815903 752430057114

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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