Основным маршрутом Транссибирской железнодорожной магистрали принято
считать маршрут следования фирменного поезда «Россия»
Москва–Владивосток, пролегающий через Нижний Новгород, Киров, Пермь
и Екатеринбург. Поезд доезжает от Москвы до Екатеринбурга за 25 часов
41 минуту.
Поезд «Урал» следует по южной ветке Транссиба через Казань и
преодолевает свой путь за 25 часов 25 минут. Быстрее доехать на поезде из
Москвы в Екатеринбург нельзя.
Выше приведена схема железных дорог между Москвой (M) и Екатеринбургом (Y). На ней видно, что на пути следования поездов «Россия» (верхняя линия на схеме) и «Урал» (нижняя линия) лежат крупные реки: Волга, Вятка и Кама. Первый поезд пересекает их, соответственно, в Нижнем Новгороде (1), в Котельниче (2) и в Перми (3). Второй поезд делает это, соответственно, в 35 километрах к западу от Казани (4), в Вятских Полянах (5) и в Сарапуле (6).
На схеме также изображены прямые ветки, соединяющие некоторые из этих городов.
Кроме пассажирских поездов, по этим железным дорогам проходят
товарные поезда, которые могут следовать по четырём маршрутам:
- Москва – Нижний Новгород – Котельнич – Сарапул – Екатеринбург
- Москва – Казань – Вятские Поляны – Сарапул – Екатеринбург
- Москва – Казань – Котельнич – Пермь – Екатеринбург
- Москва – Нижний Новгород – Вятские Поляны – Пермь – Екатеринбург
Министр путей сообщения хочет организовать движение товарных поездов таким образом,
чтобы грузопоток из Москвы в Екатеринбург был максимально возможным.
Он знает, что «узким местом» на пути поездов являются мосты через
изображённые на схеме реки. Для каждого из них известна
пропускная способность, равная количеству тонн груза,
которое можно перевезти через этот мост в течение суток. Зная пропускные
способности мостов, помогите министру решить эту задачу.
Исходные данные
Единственная строка содержит пропускные способности мостов в Нижнем
Новгороде, в Котельниче, в Перми, близ Казани, в Вятских Полянах и в
Сарапуле. Все пропускные способности являются целыми числами и лежат в
пределах от 1 до 109.
Результат
Определите суточный объём грузов, отправляемых из Москвы по
каждому из описанных выше маршрутов, чтобы суммарный грузопоток
из Москвы в Екатеринбург был максимальным.
Выведите эти четыре числа через пробел, с точностью до 10−3. Если
задача имеет несколько решений, выведите любое из них.
Пример
исходные данные | результат |
---|
70 30 60 100 20 50
| 20.000 10.000 10.000 10.000
|
Автор задачи: Александр Ипатов
Источник задачи: XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.