Задача 45: Монеты
Имеются монеты c различными фиксированными номиналами, выраженными в
копейках (например, 3 и 5 копеек) в достаточном количестве. Написать
программу COINS.*, которая:
а) определяет, можно ли представить заданную сумму S (выраженную в
копейках), пользуясь монетами заданных номиналов,
б) если это возможно, то представляет эту сумму с помощью
минимального количества монет.
Входные данные: Входной файл COINS.DAT содержит в первой
строке сумму S (0 < S < 1000000000), во второй строке - N -
количество различных номиналов (0 < S < 20), а в следующих N строках
- А1 ... АN - номиналы (в порядке возрастания), которые можно
использовать (0 < A1 < A2 < ... < AN < 1000000000).
Выходные данные: Выходной файл COINS.SOL должен содержать в
первой строке знак "+", если заданную сумму S можно представить, и
знак "-", если нельзя. Если представленная сумма существует, то
следующие N строк должны содержать количества монет каждого
номинала, которые необходимы для представления суммы S с помощью
минимального количества монет.
Примеры ввода и вывода
Представить 514 копеек с помощью монет номиналом в 3 и 5 копеек
COINS.DAT:
514
2
3
5
COINS.SOL:
+
3
101
Представить 27 копеек с помощью монет номиналом в 5 и 13 копеек
COINS.DAT:
27
2
5
13
COINS.SOL:
-
Решение:
Для решения этой задачи нам понадобится знать, как находить НОД. Для
этого надо прочитать задачу Банки.
Итак, найдем НОД номиналов всех монет. Если необходимая сумма не
делится на НОД нацело, то сразу выводим "-" (мы никак не можем
набрать 5 рублей монетками в 2 и 4 рубля! Монеты в 4 рубля - моя
идея.). Если же необходимая сумма делится на НОД без остатка, то
придется действовать хитро:
Возьмем монету с наибольшим номиналом, возьмем наибольшее количество
монет, так чтобы их сумма не превышала искомую сумму. Теперь
посчитаем НОД оставшихся монет. Если остаток искомой суммы от тех
денег, которые мы собрали, не делится на НОД, то уменьшим количество
монет с наибольшим номиналом на 1 и снова проверим, делится ли
остаток на НОД. Если делится - то переходим к следующей монете, если
нет - то опять уменьшаем на 1 количество монет. Если в какой то
момент количество монет стало отрицательным, то выводим "-" и
выходим. Если вся сумма выразилась в определенном количестве монет
разных номиналов, то выводим "+" и количество монет разного номинала
(для хранения количества монет удобно организовать массив).
Очередная задача решена!
Далее
ð
