Внекотором государстве в обращении находятся банкноты определенных номиналов. национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. национальному банку решить эту . формат ввода первая строка входных данных содержит натуральное число n не превосходящее 100 — количество номиналов банкнот в обращении. вторая строка входных данных содержит n различных натуральных чисел x1, x2, …, xn, не превосходящих 10 в 6 степени — номиналы банкнот. третья строчка содержит натуральное число s, не превосходящее 10 в 6 степени — сумму, которую необходимо выдать. формат вывода в первую строку выходного файла выведите минимальное число слагаемых (или -1, если такого представления не существует). во вторую строку выведите это представление в любом порядке. пример ввод 5 1 3 7 12 32 40 вывод 3 32 7 1

162

374

Посмотреть ответы 3

Ответы на вопрос:

Charafoxcoteyca34

Информатика

4,8(89 оценок)

Попробую. начало ввод количества номиналов 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 конец если конец вечного цикла конец подпрограммы

dodpddpfp

Информатика

4,8(7 оценок)

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. тестовые решения контрольный пример: 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