Ограничение по времени: 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, d1, s1, p1, d2, s2, p2.
- Определяем, какие рейсы подходят (могут вместить всех): подходит1 = (s1 >= n), подходит2 = (s2 >= n).
- Если ни один doesn’t подходить: вывести -1.
- Если подходит только один рейс (только 1 или только 2): взять этот рейс.
- Если подходят оба рейса:
- Сравниваем дни прибытия: если d1 > d2, выбрать рейс 1 (он с более поздним днём).
- Если d2 > d1, выбрать рейс 2.
- Если дни равны (d1 == d2), сравниваем цены: если p1 < p2 — выбрать 1, если p2 < p1 — выбрать 2.
- Если цены равны (p1 == p2) и дни равны, оба рейса равноправны — вывести оба номера: "1 2".
- После выбора рейса или рейсов рассчитываем минимальную стоимость: n * price выбранного рейса(ов). Выводим стоимость на первую строку и номера подходящих рейсов на вторую строку (один номер или несколько через пробел).
Применим к примерам из условия:
Пример 1:
- Ввод: n=9, d1=10, s1=12, p1=1000, d2=12, s2=9, p2=500.
- Подходят оба рейса? да, s1>=9 и s2>=9.
- Сравниваем дни: d2 (12) больше d1 (10) → выбрать рейс 2.
- Цена: 9 * 500 = 4500.
- Вывод:
- 4500
- 2
Пример 2:
- Ввод: n=16, d1=30, s1=25, p1=5612, d2=30, s2=19, p2=5612.
- Подходят оба рейса? да, s1>=16 и s2>=16.
- Дни равны (30 и 30). Сравниваем цены: p1 = p2 = 5612 → цены равны.
- Таким образом оба рейса равноправны. Выводим оба номера.
- Цена: 16 * 5612 = 89792.
- Вывод:
- 89792
- 1 2
Если ни один рейс не подходит, просто выведите -1. В условиях гарантируется, что хотя бы один рейс подходит, но логика учитывает и такой случай.
Итоговый формат вывода:
- Первая строка: минимальная стоимость (или -1).
- Вторая строка: номера подходящих рейсов (один номер, или "1 2" если оба подходят и являются равноправными по условиям).
