Минимальная стоимость доставки
У медицинской компании есть $N$ пунктов приёма биоматериалов на анализ. Все пункты расположены вдоль автомагистрали и имеют номера, соответствующие расстоянию от нулевой отметки до конкретного пункта. Известно количество пробирок, которое ежедневно принимают в каждом из пунктов. Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 46 штук. Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Компания планирует открыть лабораторию в одном из пунктов. Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории на количество контейнеров с пробирками. Общая стоимость перевозки за день равна сумме стоимостей перевозок из каждого пункта в лабораторию. Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом, что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Входные данные: два файла, файл A и файл B. Каждый файл в первой строке содержит число $N$ ($1 \leq N \leq 10\,000\,000$). В каждой из следующих $N$ строк находятся два натуральных числа: номер пункта и количество пробирок в этом пункте. Количество пробирок в каждом пункте не превышает 1000. Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем — для файла B.
Типовой пример организации данных во входном файле:
$6$
$1\ 100$
$2\ 200$
$5\ 4$
$7\ 3$
$8\ 2$
$10\ 190$
При типовых исходных данных и вместимости транспортировочного контейнера, составляющей 96 пробирок, компании выгодно открыть лабораторию в пункте 2. В этом случае сумма транспортных затрат составит $1 \cdot 2 + 3 \cdot 1 + 5 \cdot 1 + 6 \cdot 1 + 8 \cdot 2$. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Условие как в банке ФИПИ — открыть и сверить
| |||||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Для каждого пункта сначала определите число контейнеров: $\left\lceil \dfrac{q_i}{46} \right\rceil$.
2Наводящая — какие числа считатьуровень 2 из 3
При переходе лаборатории от одного пункта к следующему изменение стоимости можно вычислять по суммарному числу контейнеров слева и справа, не пересчитывая всю сумму.
3Прямая — фактически решениеуровень 3 из 3
Посчитайте стоимость для первой позиции, затем последовательно обновляйте её при движении лаборатории вправо и запоминайте минимум.