Билеты на метро. Не понимаю логику

Question

Билет на одну поездку в метро стоит 15 рублей, билет на 10 поездок стоит 125 рублей, билет на 60 поездок стоит 440 рублей. Пассажир планирует совершить n поездок. Определите, сколько билетов каждого вида он должен приобрести, чтобы суммарное количество оплаченных поездок было не меньше n, а общая стоимость приобретенных билетов – минимальна.

Входные данные Дано одно число n - количество поездок.

Выходные данные Выведите три целых числа, равные необходимому количеству билетов на 1, на 10, на 60 поездок.

Answer 1

Элементарно, Ватсон! :)

Берем простое жадное решение, а затем проверяем, нельзя ли заменить одинарные билеты одним на 10, потом - билеты на 10 одним на 60. Если первое условие отрицательно - проверяем, нельзя ли заменить одинарные билеты и все по 10 - на один на 60 поездок.

int main()
{
    int n, m60 = 0, m10 = 0, m1 = 0;
    cin >> n;
    m60 = n/60;    // Минимальное число на 60 поездок
    n = n % 60;    // остаток
    if (n)
    {
        m10 = n/10;   // Остаток - на 10 поездок
        m1  = n%10;   // Остаток для одинарных
    }
    if (m1*15 > 125)  // Проверяем, не имеет ли смысла заменить одинарные одним на 10
    {
        m1 = 0;
        m10++;
    }
    if (m1*15 + m10*125 > 440) // или все на 1 и 10 - одним билетом на 60
    {
        m1 = m10 = 0;
        m60++;
    }

    cout << m1 << " " << m10 << " " << m60 << endl;

}

Answer 2

Допустим n = 12 
Это 10 + 2
1-ое основание 10 (125р цена билетов)
2-ое 2 (2 * 15 = 30)
125 + 30 = оптимальная цена 

Или

Допустим n = 256 (кол-во поездок)

Делим наше n на каждый из трёх видов билетов:
Вид_1: 1 поездка = 15
Вид_2: 10 поездок = 125
Вид_3: 60 поездок = 440

И далее проверками if проверяем на целое.
1 шаг.
Если (n / Вид_3 != 0) то берём целое от деления и умножаем на 440 и получаем сумму_1
n - (Вид_3 * целое_от_деления) = получаем остаток поездок
шаг 2.
Если (n / Вид_2 != 0) то берём целое от деления и умножаем на 125 и получаем сумму_2
n - (Вид_2 * целое_от_деления) = получаем остаток поездок
шаг 3.
Если (n / Вид_3 != 0) то берём целое от деления и умножаем на 10 и получаем сумму_1
n - (Вид_1 * целое_от_деления) = получаем остаток поездок

оптимальная_цена_за_n_поездок = сумма_1 + сумма_2 + сумма_3

Для n поездок, необходимо купить билетов вида:
Вид_1 = целое от деления
Вид_2 = целое от деления
Вид_3 = целое от деления


PS Думаю этот псевдокод будет понятен :)

БЛОГ НА HUSL

Билеты на метро. Не понимаю логику

Ответы (2 шт):