Сколько билетов каждого типа нужно приобрести пассажиру, чтобы общее количество оплаченных поездок было не менее
Сколько билетов каждого типа нужно приобрести пассажиру, чтобы общее количество оплаченных поездок было не менее n и стоимость приобретенных билетов была минимальной, исходя из следующей ценовой структуры: 1 поездка — 15 рублей, 5 поездок — 70 рублей, 10 поездок — 125 рублей, 20 поездок — 230 рублей, 60 поездок — 440 рублей? Входные данные: программа получает одно натуральное число n (n ≤ 10000). Выходные данные: программа должна вывести пять целых чисел, обозначающих количество билетов каждого типа.
19.12.2023 19:53
Написать свой ответ:
Описание: Для решения этой задачи мы можем воспользоваться жадным алгоритмом. Жадный алгоритм заключается в том, чтобы всегда выбирать лучший вариант в текущий момент, не задумываясь о будущем. Когда мы разделяем общую сумму на поездки разных типов, нам нужно минимизировать стоимость приобретенных билетов. Используя этот метод, мы можем сначала купить наибольшее количество билетов на 60 поездок, затем по возрастанию - 20 поездок, 10 поездок, 5 поездок и 1 поездку, чтобы достичь необходимого общего количества поездок.
Дополнительный материал:
Входные данные: n = 100
Выходные данные: 1, 0, 0, 0, 40
Совет:
Когда вы решаете задачу, вы можете сначала проверить, достаточно ли купить наибольшее количество билетов на 60 поездок, чтобы достичь общего количества поездок. Если нет, увеличьте количество приобретаемых билетов на 20 поездок, а затем проверьте снова. Продолжайте делать это для 10 поездок, 5 поездок и 1 поездки, пока не достигнете необходимого значения для общего количества поездок.
Дополнительное упражнение:
Сколько билетов каждого типа нужно приобрести, чтобы общее количество оплаченных поездок было не менее 200 и стоимость приобретенных билетов была минимальной?