Задача 6. Оптом – дешевле! В Москве начал работать новый оператор сотовой связи, предоставляющий доступ в интернет посредством технологии 3G. Новый оператор предлагает простые и невысокие тарифы, в частности, один мегабайт интернет-трафика стоит 1 рубль. Кроме того, оператор предлагает покупать оптовые пакеты трафика – есть два предложения: купить пакет трафика на А мегабайт за В рублей и купить пакет трафика на С мегабайт за D рублей. Таня планирует использовать в течение месяца N мегабайт интернет-трафика. Определите минимальную сумму, которую придётся ей заплатить. Таня может приобретать любое количество каждых из двух предлагаемых пакетов, а также оплачивать трафик по тарифу «1 рубль за мегабайт». Таня может приобретать пакеты интернет-трафика и в том случае, если суммарный оплаченный трафик будет более N мегабайт, если это выйдет дешевле. Программа получает на вход пять натуральных чисел N, A, B, C, D, записанных в отдельных строках, не превосходящих 500 000 каждое. Гарантируется, что A > B и C > D. Программа должна вывести одно целое число – минимальную сумму, которую нужно заплатить для приобретения N мегабайт трафика. Примеры входных и выходных данных Ввод 35 10 9 20 17 55 30 20 20 16 Вывод 31 40 Примечание Пакет на 10 мегабайт стоит 9 рублей, пакет на 20 мегабайт стоит 17 рублей. Для оплаты 35 мегабайт нужно купить пакет на 10 мегабайт и пакет на 20 мегабайт, а за оставшиеся 5 мегабайт заплатить 5 рублей. Пакет на 30 мегабайт стоит 20 рублей, пакет на 20 мегабайт стоит 16 рублей. Для оплаты 55 мегабайт нужно купить два пакета на 30 мегабайт, что суммарно будет стоить 40 рублей.

Решение:

Задача сводится к минимизации затрат на покупку N мегабайт интернет-трафика, учитывая возможность покупки пакетов и оплаты по тарифу «1 рубль за мегабайт».

Предлагаются два варианта пакетов:

1. Пакет на A мегабайт за B рублей.
2. Пакет на C мегабайт за D рублей.

Также есть возможность оплачивать трафик по тарифу 1 рубль за мегабайт.

Гарантируется, что A > B и C > D, что означает, что покупка пакетов выгоднее, чем оплата по тарифу за каждый мегабайт в отдельности, если покупать полный пакет.

Для определения минимальной суммы необходимо рассмотреть все возможные комбинации покупки пакетов и оплаты по тарифу «1 рубль за мегабайт».

Пример 1:

Ввод: N=35, A=10, B=9, C=20, D=17

Анализ:

• Тариф «1 рубль за мегабайт»: 35 Мб * 1 руб/Мб = 35 рублей.
• Пакет 1 (10 Мб за 9 руб) + Тариф (25 Мб за 25 руб) = 9 + 25 = 34 рубля.
• Пакет 2 (20 Мб за 17 руб) + Тариф (15 Мб за 15 руб) = 17 + 15 = 32 рубля.
• Два пакета 1 (20 Мб за 18 руб) + Тариф (15 Мб за 15 руб) = 18 + 15 = 33 рубля.
• Пакет 1 (10 Мб за 9 руб) + Пакет 2 (20 Мб за 17 руб) + Тариф (5 Мб за 5 руб) = 9 + 17 + 5 = 31 рубль.
• Два пакета 2 (40 Мб за 34 руб) – избыток, но может быть дешевле. 40 Мб > 35 Мб, стоимость = 34 рубля.

Минимальная сумма – 31 рубль.

Пример 2:

Ввод: N=55, A=30, B=20, C=20, D=16

Анализ:

• Тариф «1 рубль за мегабайт»: 55 Мб * 1 руб/Мб = 55 рублей.
• Пакет 1 (30 Мб за 20 руб) + Тариф (25 Мб за 25 руб) = 20 + 25 = 45 рублей.
• Пакет 2 (20 Мб за 16 руб) + Тариф (35 Мб за 35 руб) = 16 + 35 = 51 рубль.
• Два пакета 1 (60 Мб за 40 руб) – избыток, но может быть дешевле. 60 Мб > 55 Мб, стоимость = 40 рублей.
• Пакет 1 (30 Мб за 20 руб) + Пакет 2 (20 Мб за 16 руб) + Тариф (5 Мб за 5 руб) = 20 + 16 + 5 = 41 рубль.
• Два пакета 2 (40 Мб за 32 руб) + Тариф (15 Мб за 15 руб) = 32 + 15 = 47 рублей.
• Три пакета 1 (90 Мб за 60 руб) – избыток, стоимость 60 руб.
• Пакет 1 (30 Мб за 20 руб) + Пакет 1 (30 Мб за 20 руб) = 60 Мб за 40 руб.

Минимальная сумма – 40 рублей.

Алгоритм:

Для каждого возможного количества пакетов первого типа (от 0 до N/A) и второго типа (от 0 до N/C) нужно рассчитать общую стоимость. Также необходимо учесть, что пакеты могут быть куплены в избытке, если это дешевле. Минимальная стоимость получается из сравнения:

1. Покупки N мегабайт по тарифу «1 рубль за мегабайт».
2. Покупки пакетов так, чтобы суммарный объём трафика был не менее N мегабайт, и минимизировать стоимость.

Сложность задачи в том, что пакеты можно комбинировать, и выгоднее может оказаться покупка большего объёма трафика, чем требуется, если это удешевляет общую стоимость.

Минимальная сумма будет определяться как минимум из:

• N (оплата по тарифу «1 рубль за мегабайт»).
• i * B + j * D + max(0, N - i*A - j*C), где i и j — количество купленных пакетов первого и второго типа соответственно, и мы перебираем все i и j такие, что i*A + j*C >= N (включая случаи, когда i*A + j*C > N, и мы оплачиваем только N, если это дешевле, что упрощается до i*B + j*D, если i*A + j*C >= N).

Также нужно рассмотреть случаи, когда куплено i пакетов типа A и j пакетов типа C, и их суммарный объём i*A + j*C превышает N, но стоимость i*B + j*D меньше, чем N.

Ответ: 31 (для первого примера), 40 (для второго примера).