В некотором государстве в обращении находятся банкноты определенных номиналов....

Question

В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу.
Формат ввода

Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, …, xN, не превосходящих 10 в 6 степени — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 10 в 6 степени — сумму, которую необходимо выдать.
Формат вывода

В первую строку выходного файла выведите минимальное число слагаемых (или -1, если такого представления не существует). Во вторую строку выведите это представление в любом порядке.
Пример

Ввод
5
1 3 7 12 32
40
Вывод
3
32 7 1

Answer 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
Конец Если
Конец вечного Цикла
Конец подпрограммы

Comments

Не пойму, как это должно работать. Объявлены массивы X и Y размером N элементов (по числу номиналов банкнот). Поскольку в цикле ввода индекс меняется от 1 до N, можно сделать вывод, что нумерация элементов идет с единицы. Далее, k - это количество банкнот и первоначально оно нулевое. Оператор Y[k]:=X[i] в случае, если сумма S окажется больше максимального номинала банкноты, произойдет ошибка по нарушению индексации при попытке обратиться к Y[0].

---

Я предполагал вот как. Массив Y сначала пустой, мы находим очередную банкноту, которая меньше S, и записываем ее в Y. Возможно, что нужно проверку Если S < X(1) делать в самом начале цикла по S, перед оператором i = N. Сейчас перепишу.

---

Так наверное более правильно будет. Все сразу не предусмотришь, приходится отлаживать!

---

Кстати, есть шутка. Отлаживание программы - это избавление ее от лажи.

---

Вторая ошибка - это
Если S < X(1), то
S = 0: k = -1
Если сумму смогли выдать, то S=0 и по этому условию получаем k=-1...

---

Вы пишете в синтаксисе Бейсика; не проще ли было скопировать сюда текст отлаженной программы с контрольным примером?

---

К сожалению, мне отлаживать не в чем да и времени нет. А вот насчет "Если сумму смогли выдать" я не понял. Если запрашиваемая сумма S меньше, чем самая маленькая бумажка, то размен невозможен и надо поставить k = -1 и выйти из цикла.

---

Сейчас верно, Вы же поменяли решение. А мой комментарий был для исходного текста. А отладить можно в любой Windows, сохраните текст в Бейсике с расширением vbs и запустите)

---

Если особенностей VBScript не знаете - их легко найти в Интернет. Главная - простые переменные не описываются, а получают тип при присваивании. И в программе на ставится финальный end

---

*НЕ ставится

Answer 2

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