Ограничение по времени: 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
Решение задачи по заданным правилам
Цель: определить минимую общую стоимость поездки и номера рейсов, которыми можно отправить всех студентов, учитывая правила выбора рейсов.
Как действовать (пошагово)
Признаки пригодности рейсов:
- рейс 1 пригоден если s1 >= n
- рейс 2 пригоден если s2 >= n
Если ни один рейс не подходит → вывести -1 (но в условии гарантировано, что хотя бы один подходит).
Если подходит только один рейс:
- выбираем этот рейс. Стоимость = n * p_i. Номера рейсов: только i.
Если подходят оба рейса:
- сравнить дни прибытия d1 и d2:
- если d1 > d2: выбираем рейс 1 (позднее прибытие)
- если d2 > d1: выбираем рейс 2
- если d1 == d2: пришли в один день
- если p1 < p2: выбираем рейс 1
- если p2 < p1: выбираем рейс 2
- если p1 == p2: оба рейса равноправны → можно отправлять и тем, и другим, цена одинакова
- сравнить дни прибытия d1 и d2:
Формирование вывода:
- первая строка: общая минимальная стоимость = n * выбранная_цена
- вторая строка: номера подходящих рейсов (если выбран один — просто его номер, если оба равноправны — “1 2” в порядке возрастания)
Примеры на основе приведённых входов Пример 1: Ввод: n=9 d1=10, s1=12, p1=1000 d2=12, s2=9, p2=500
Рассуждение:
- оба рейса подходят (12 >= 9 и 9 >= 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
Рассуждение:
- оба рейса подходят
- дни равны, цены равны → оба рейса допустимы
- стоимость = 16 * 5612 = 89792 Вывод: 89792 1 2
Итоговый алгоритм реализуем в любом удобном языке с учётом вышеописанных условий.
