В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого ном...
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу.
Формат ввода
Первая строка входных данных содержит натуральное число 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
Конец Если
Конец вечного Цикла
Конец подпрограммы
Гость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 (sum0) 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
Не нашли ответ?
Похожие вопросы