Problem
Znalezienie minimalnej liczby banknotów/monet (z ustalonej puli nominałów) potrzebnych do wypłacenia danej kwoty. Użyj programowania dynamicznego. Zakładamy, że liczba banknotów/monet o ustalonych nominałach jest nieograniczona.
Wejście
W pierwszej linii liczba naturalna 0 < k = kwota do wypłacenia.
W drugiej linii liczba naturalna 1 <= n <= 1000, w trzeciej linii n oddzielonych spacjami liczb naturalnych 0 < A[1],...,A[n] = ustalone nominały.
Wyjście - dwie możliwości
(1) Gdy rozwiązanie nie istnieje, na wyjściu powinien się pojawić jedynie napis 'NIE'.
(2) W przeciwnym wypadku: liczba naturalna t = minimalna liczba banknotów/monet potrzebnych do wypłacenia kwoty k;
w drugiej linii, oddzielone spacjami liczby S[1],...,S[t] = nominały użyte do wypłacenia kwoty k (tj. S[1]+...+S[t]=k). Wartości S[1],...,S[t] posortowane nierosnąco.
Przykładowe wejście I
23
3
2 1 5
Wynik I
6
5 5 5 5 2 1
Przykładowe wejście II
5
2
2 4
Wynik II
NIE
