e-olymp 107. Компакт-диски

Постановка задачи

Чистые компакт-диски продают в трёх видах упаковок. Упаковка из 100 дисков стоит 100 грн., из 20 дисков — 30 грн., а один диск стоит 2 грн. Какую минимальную сумму нужно истратить для покупки [latex]N[/latex] таких дисков?

Входные данные:

Единственное число [latex]N[/latex] — количество дисков. Значение [latex]N[/latex] натуральное, не больше 1000.

Выходные данные:

Искомая минимальная сумма в гривнах.

Тесты

Входные данные Выходные данные
1 0 0
2 163 196
3 238 260
4 298 300

Решение

Описание решения

Задача может быть решена по алгоритму «купить максимальное количество упаковок из 100, потом из 20 дисков, а потом докупать по одному диску, чтобы получить требуемые для покупки [latex]N[/latex] дисков». Такой алгоритм можно записать формулой: [latex](N / 100) * 100 + (N \% 100 / 20) * 30 + 2 * (N \% 20)[/latex].

Однако такой подход к решению задачи в некоторых случаях не даст правильного результата — минимальную сумму в гривнах, потому что иногда покупка большего количества дисков, чем требует условие, дешевле, чем покупка точного количества дисков.

К примеру, если необходимо купить 96 дисков, куда дешевле купить за 100 гривен упаковку, содержащую 100 дисков, чем 4 упаковки по 20 дисков и отдельно еще 16 дисков, что в общей стоимости даст 152 гривны.

Поэтому сперва следует проверить, не будет ли покупка большего количества дисков дешевле. Для этого используются условия if (N % 100 >= 65) и if (N % 20 > 15), где 65 и 15 — лимит количества дисков, при превышении которого покупка упаковок из 100 и 20 дисков соответственно — дешевле.

Посмотреть решение задания можно на сайте e-olymp.

Посмотреть, как работает программа со входными данными 238 можно на сайте ideone.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *