Постройте жадный алгоритм, который получает на вход натуральное число n и за время O(n) находит минимальное число монет номиналом 1 копейка, 5 копеек, 10 копеек и 25 копеек, с помощью которых можно выдать сдачу в n копеек. (Как всегда, нужно описать алгоритм, доказать его корректность и оценку на время работы. Приводить псевдокод нужно только в том случае, если вам кажется, что он поможет читателю лучше понять ваш алгоритм.)
Приведите пример номиналов монет, для которых жадный алгоритм построит неоптимальное решение. В множество номиналов должна входить монета номиналом 1 копейка, чтобы любую сумму n можно было разменять этими монетами.
