Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Даниилу необходимо отправить n студентов на олимпиаду в Саратов. Для этого доступны два автобусных рейса,…
Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Даниилу необходимо отправить n студентов на олимпиаду в Саратов. Для этого доступны два автобусных рейса, каждый из которых характеризуется днём прибытия, количеством свободных мест и стоимостью билета. Студентов можно отправить только тем рейсом, в котором имеется не менее n свободных мест. Если подходящих рейсов несколько, следует выбрать рейс с наиболее поздним днём прибытия — это позволит сэкономить на размещении в гостинице. Если после этого выбора остаётся более одного варианта (то есть оба рейса прибывают в один и тот же день и оба вмещают всех студентов), предпочтение отдаётся более дешёвому рейсу. Помогите Даниилу. Определите минимальную стоимость поездки, а также номера рейсов, которыми можно отправить студентов. Если ни один рейс не подходит, то выведите -1. Формат входных данных Первая строка содержит целое число n (1⩽n⩽100 ) — количество студентов. Вторая строка содержит целое число d1 (1⩽d1⩽30 ) — день прибытия первого рейса. Третья строка содержит целое число s1 (0⩽s1⩽100 ) — количество свободных мест на первом рейсе. Четвёртая строка содержит целое число p1 (1⩽p1⩽10000 ) — стоимость билета на первый рейс. Пятая строка содержит целое число d2 (1⩽d2⩽30 ) — день прибытия второго рейса. Шестая строка содержит целое число s2 (0⩽s2⩽100 ) — количество свободных мест на втором рейсе. Седьмая строка содержит целое число p2 (1⩽p2⩽10000 ) — стоимость билета на второй рейс. Формат выходных данных В первой строке выведите одно целое число — минимальную стоимость поездки. В следующих строках выведите одно или несколько целых чисел — номера подходящих рейсов. Гарантируется, что хотя бы один рейс подходит. Ввод Вывод 9 10 12 1000 12 9 500 4500 2 16 30 25 5612 30 19 5612 89792 1 2
Задача сводится к выбору одного рейса среди двух, на который можно отправить всех студентов, с учетом правил:
- можно отправить только на рейс, где свободных мест не меньше n;
- если подходящих рейсов несколько, выбирается рейс с наибольшей днём прибытия;
- если после этого остаётся несколько рейсов (то есть они приезжают в один и тот же день и способны взять всех), выбирается рейс с наименьшей ценой; если и цены совпадают, можно оставить оба рейса.
Вывод: сначала минимальная стоимость поездки, затем номера подходящих рейсов (если их несколько, выводим все, которые дают минимальную стоимость после применения правил).
Пошаговый разбор:
- Соберите кандидатов — рейсы, у которых s_i >= n.
- Если таких рейсов нет — вывод -1 (но задача гарантирует, что хотя бы один рейс подходит).
- Найдите максимальный день прибытия среди кандидатов. Оставьте только рейсы с этим днём.
- Среди рейсов с максимальным днём найдите минимальную цену p_min.
- Все рейсы с этим днём и ценой p_min — это и есть искомые варианты. Их номера выведите во второй строке (в порядке возрастания).
Пример решения для приведённых в задаче данных (один из тестов):
Данные теста:
- n = 9
- Рейс 1: d1 = 10, s1 = 12, p1 = 1000
- Рейс 2: d2 = 12, s2 = 9, p2 = 500
Шаги:
- s1 >= n? 12 >= 9 — да; s2 >= n? 9 >= 9 — да. Оба рейса подходят.
- Максимальный день: max(10, 12) = 12. Оставляем рейс 2.
- Среди оставшихся (только рейс 2) минимальная цена: 500.
- Итог: минимальная стоимость поездки = 500; подходящие рейсы: 2.
Формат вывода:
- Первая строка: минимальная стоимость поездки (целое число).
- Вторая строка: номера подходящих рейсов (одна или несколько чисел, через пробел). Если подходило два рейса и оба дают минимальную стоимость, выведите оба их номера.
Пояснение по границам и примерам:
- Если оба рейса имеют одинаковый день прибытия и оба могут взять всех (s1 >= n и s2 >= n, d1 == d2), то из рейсов выбирается тот, у которого меньшая цена. Если цены совпадают, выводим оба номера — это соответствует ситуации, когда оба рейса одинаково выгодны и удовлетворяют условиям.
- Гарантируется, что хотя бы один рейс подходит, поэтому выход -1 не будет в таких тестах, но кодить логику следует именно так.
Если хочешь, могу привести готовый мини-код на любом языке (например, Python или C++) реализующий этот алгоритм.
