|
КЕГЭ-27. Основная волна 2022-I (Источник kompege.ru задание 4605)
Тетрадь с разбором аналогичной задачи
У медицинской компании есть N пунктов приёма биоматериалов на анализ.
Все пункты расположены вдоль автомагистрали и имеют номера,
соответствующие расстоянию от нулевой отметки до конкретного пункта.
Известно количество пробирок, которое ежедневно принимают в каждом из пунктов.
Пробирки перевозят в специальных транспортировочных контейнерах вместимостью не более 36 штук.
Каждый транспортировочный контейнер упаковывается в пункте приёма и вскрывается только в лаборатории.
Компания планирует открыть лабораторию в одном из пунктов.
Стоимость перевозки биоматериалов равна произведению расстояния от пункта до лаборатории
на количество контейнеров с пробирками. Общая стоимость перевозки за день равна
сумме стоимостей перевозок из каждого пункта в лабораторию.
Лабораторию расположили в одном из пунктов приёма биоматериалов таким образом,
что общая стоимость доставки биоматериалов из всех пунктов минимальна.
Определите минимальную общую стоимость доставки биоматериалов из всех пунктов приёма в лабораторию.
Входные данные
Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит
число N (1 ≤ N ≤ 10 000 000) – количество пунктов приёма биоматериалов.
В каждой из следующих N строк находится два числа: номер пункта и количество пробирок в этом пункте
(все числа натуральные, количество пробирок в каждом пункте не превышает 1000).
Пункты перечислены в порядке их расположения вдоль дороги, начиная от нулевой отметки.
Типовой пример организации данных во входном файле
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.
|