Постановка задачи
Чистые компакт-диски продают в трёх видах упаковок. Упаковка из 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 |
Решение
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
import java.util.*; class Task2 { public static void main (String[] args) { int N; Scanner in = new Scanner(System.in); N = in.nextInt(); if (N % 100 >= 65) N = 100 * (N / 100 + 1); if (N % 20 > 15) N = 20 * (N / 20 + 1); System.out.println((N / 100) * 100 + (N % 100 / 20) * 30 + 2 * (N % 20)); } } |
Описание решения
Задача может быть решена по алгоритму «купить максимальное количество упаковок из 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.