![>](style_images/1/nav_m.gif)
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.224.30.86] |
![]() |
|
Сообщ.
#1
,
|
|
|
Билет на одну поездку в метро стоит 15 рублей, билет на 10 поездок стоит 125 рублей, билет на 60 поездок стоит 440 рублей. Пассажир планирует совершить n поездок. Определите, сколько билетов каждого вида он должен приобрести, чтобы суммарное количество оплаченных поездок было не меньше n, а общая стоимость приобретенных билетов – минимальна.
Дано одно число n - количество поездок. Выведите три целых числа, равные необходимому количеству билетов на 1, на 10, на 60 поездок. |
Сообщ.
#2
,
|
|
|
Код попрошу попробовать написать самостоятельно. Но вариант решения задачи расскажу как получить ... На самом деле все просто - все типы билетов имеют разную "удельную стоимость поездки". И для решения задачи нам важно сперва выкупить все билеты наименьшей удельной стоимости, потом чуть большей, ну и далее самой большой.
Пример: Пусть n=1007 поездок, на первом шаге выкупаем все билеты наименьшей удельной стоимости (это билеты на 60 поездок) 1007/60 = 16 билетов, остаток от деления 47 на втором шаге выкупаем билеты на 10 поездок 47/10 = 4 билета, остаток от деления 7 на третьем шаге выкупаем выкупаем оставшиеся билеты на одну поездку в количестве 7 шт Итого: 7, 4, 16 Для программирования на С++ нужно посмотреть только целочисленное деление и деление по модулю, ну и ввод-вывод, если это для задания критично. |
![]() |
Сообщ.
#3
,
|
|
JoeUser, на 59 поездок можно купить один билет за 440 р. Твой подход (5х125 + 9х15) дороже.
|
Сообщ.
#4
,
|
|
|
MIF, согласен, нужно вводить коррективы. Выбирать на каждом шаге "купить с неистраченными поездками" или "купить ровно по поездкам" относительно цены. Но дальше мне лень это корректировать.
|
![]() |
Сообщ.
#5
,
|
|
На одном из форумов пометили как верное решение на Python
![]() ![]() n = int(input('n = ')) result = [] for v in (60, 20, 10, 5, 1): x = n // v result.append(x) n -= v * x print(*reversed(result)) |