В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал л
юбую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу. Формат ввода
Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, …, xN, не превосходящих 10 в 6 степени — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 10 в 6 степени — сумму, которую необходимо выдать. Формат вывода
В первую строку выходного файла выведите минимальное число слагаемых (или -1, если такого представления не существует). Во вторую строку выведите это представление в любом порядке. Пример
Попробую. Начало Ввод количества номиналов N Объявляем массивов X(N), Y(N) Цикл по i от 1 до N Ввод очередного номинала X(i) Конец цикла по i Ввод суммы для выдачи S Подпрограмма сортировки массива X(N) по возрастанию. Например, пузырьковой сортировкой. k = 0 ' k - это количество банкнот Цикл, пока S > 0
Если S < X(1), то ' Если остаток меньше самого маленького номинала S = 0: k = -1 ' то выдать полную сумму невозможно Выход сразу из цикла по S Конец Если
i = N Цикл, пока X(i) > S i = i - 1 Конец цикла по X(i) Y(k) = X(i) ' записываем очередную банкноту в массив Y(N) S = S - X(i) ' определяем остаток k = k + 1 ' увеличиваем счетчик банкнот Конец цикла по S Если k = 0, то k = -1 ' выдать сумму не смогли Вывод k Если k > 0, то ' Если сумму можно выдать Цикл по i от 1 до k Вывод Y(i) + " " Конец цикла по i Конец Если Конец
Алгоритм пузырьковой сортировки: Начало подпрограммы F = True ' Это булева переменная - признак успешности сортировки Цикл вечный без всяких условий Если F = True, то F = False Цикл по i от 1 до N-1 Если X(i) > X(i+1), то ' если два соседних числа не отсортированы Q = X(i) : X(i) = X(i+1) : X(i+1) = Q ' меняем местами эти числа F = True Конец Если Конец цикла по i Иначе Выход из Цикла ' Если F = False Конец Если Конец вечного Цикла Конец подпрограммы
Const nn=100; { предельное количество номиналов банкнот } type bnk=longint; var nom,res:array[1..nn] of bnk; i,n,koln:integer; sum:bnk;
procedure Sort(n:integer); var i,j:integer; t:bnk; begin for i := 1 to n-1 do for j := 1 to n-i do if nom[j] > nom[j+1] then begin t := nom[j]; nom[j] := nom[j+1]; nom[j+1] := t end end;
begin Readln(n); for i:=1 to n do Read(nom[i]); Readln(sum); Sort(n); koln:=0; i:=n; while sum>0 do begin while nom[i]>sum do Dec(i); Inc(koln); res[koln]:=nom[i]; sum:=sum mod nom[i]; if (sum<nom[1]) and (sum<>0) then begin sum:=0; koln:=-1 end end; if koln=0 then koln:=-1; Writeln(koln); for i:=1 to koln do Write(res[i],' '); Writeln end.