Ошибка.
Попробуйте повторить позже
У медицинской компании есть 
пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль
автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно
количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных
транспортировочных контейнерах вместимостью 
пробирок. Каждый транспортировочный контейнер упаковывается в
пункте приёма и вскрывается только в лаборатории. Компания планирует открыть лабораторию в одном из пунктов.
Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров
с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию.
Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки
биоматериалов из всех пунктов минимальна. Определите минимальную общую стоимость доставки биоматериалов из всех
пунктов приёма в лабораторию.
Входные данные:
Даны два входных файла — 
и 
, каждый из которых содержит в первой строке число 
(
) –
количество пунктов приёма биоматериалов, и число 
(
) – вместимость транспортировочного контейнера.
Каждая из следующих 
строк содержит два натуральных числа: номер пункта и количество пробирок (не превышающее
10000). Пункты перечислены в произвольном порядке.
Пример входного файла:
6 96
5 4
7 3
1 100
10 190
2 200
8 2
При таких исходных данных (вместимость транспортировочного контейнера равна 96 пробирок) компании выгодно
открыть лабораторию в пункте 2. В том случае сумма транспортных затрат составит 
.
Ответ: 32.
Неэффективное решение
f = open(’27_A.txt’) n, v = map(int, f.readline().split()) a = [] for i in range(n): s, k = map(int, f.readline().split()) # кол-во сумок if k % v == 0: c = k//v else: c = k//v + 1 a.append([s, c]) a.sort() min_sum = 10**20 for i in range(n): new_sum = 0 for j in range(n): new_sum += abs(a[i][0]-a[j][0])*a[j][1] min_sum = min(min_sum, new_sum) print(min_sum)
Ээффективное решение
f = open(’27_B.txt’) n, v = map(int, f.readline().split()) a = [] for i in range(n): s, k = map(int, f.readline().split()) # кол-во сумок if k % v == 0: c = k//v else: c = k//v + 1 a.append([s, c]) a.sort() # префиксные суммы количества сумок в первых n пунктах bags = [0]*n bags[0] = a[0][1] for i in range(1,n): bags[i] = bags[i-1] + a[i][1] #стоимость доставки в нулевом пункте s = 0 for j in range(n): s += abs(a[0][0]-a[j][0])*a[j][1] min_sum = s for i in range(1,n): diff = a[i][0] - a[i-1][0] #расстояние между двумя пунктами #Пересчет суммы #для предыдущих пунктов дороже, для следующих дешевле s = s + diff*bags[i-1] - diff*(bags[n-1]-bags[i-1]) #Пересчет минимума min_sum = min(min_sum,s) print(min_sum)
