Внекотором государстве в обращении находятся банкноты определенных номиналов. национальный банк хочет, чтобы банкомат выдавал любую за сумму при минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. национальному банку решить эту . формат ввода первая строка входных данных содержит натуральное число n не превосходящее 100 — количество номиналов банкнот в обращении. вторая строка входных данных содержит n различных натуральных чисел x1, x2, …, xn, не превосходящих 10 в 6 степени — номиналы банкнот. третья строчка содержит натуральное число s, не превосходящее 10 в 6 степени — сумму, которую необходимо выдать. формат вывода в первую строку выходного файла выведите минимальное число слагаемых (или -1, если такого представления не существует). во вторую строку выведите это представление в любом порядке. пример ввод 5 1 3 7 12 32 40 вывод 3 32 7 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
Конец Если
Конец вечного Цикла
Конец подпрограммы
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.
Тестовые решения
Контрольный пример:
5
1 3 7 12 32
40
3
32 7 1
Еще один пример:
8
1 5 10 50 100 500 1000 5000
4586
6
1000 500 50 10 5 1