Динамическое программирование

Набрать сумму монетками

Даны номиналы монет $1 \le a_i \le 10^9$ при $1 \le i \le 20$, и дана сумма $1 \le N \le 10^9$. Определить, какое минимальное число монет необходимо, чтобы набрать ими указанную сумму. Например, если даны номиналы монет в $a_1=2$, $a_2=3$, $a_3=10$, то набрать сумму $N=7$ можно тремя монетами: $7 = 3 + 2 + 2$, а сумму $N = 21$ оптимально можно набрать пятью: $21 = 10 + 3 + 3 + 3 + 2$.

В задаче будет три варианта по возрастанию сложности. По заданному набору номиналов монет и сумме необходимо:

  1. определить только, можно ли эту сумму набрать;
  2. определить минимальное необходимое количество монет;
  3. определить и минимальное необходимое количество монет, и перечислить сами монеты.

Формат входного и выходного файла

В первой строке файла дано число $k$ — количество различных номиналов монет. В следующих $k$ строках даны числа $a_i$. В последней строке находится число $N$. Пример из условия будет указан так (файл 1.in):

3
2
3
10
21

В выходной файл необходимо вывести, в зависимости от уровня сложности:

  1. слова YES или NO, в зависимости от того, можно ли набрать указанную сумму.
  2. одно число — минимальное необходимое количество монет для набора суммы, или -1, если это невозможно.
  3. В первой строке число, как в прошлом пункте, после этого в каждой строке по количеству монет соответствующего номинала.

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

  1. Файл 1.possible.out: 
     YES
  2. Файл 1.how-many.out: 
      5
  3. Файл 1.full-answer.out: 
      5
  1
  3
  1

    Он означает, что необходимо минимум пять монет для набора суммы, при этом монет номинала $a_1=2$ требуется взять 1 штуку, монет номинала $a_2=3$ нужно 3 штуки, монет номинала $a_3=10$~— одна штука.

Наибольшая возрастающая подпоследовательность

Разбор задачи о наибольшей возрастающей подпоследовательности

Дана последовательность целых чисел, во входном файле сначала указано количество ее элементов, потом построчно перечислены сами элементы, например,

8
6
10
2
5
9
7
8
3

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

  1. Длину максимальной возрастающей подпоследовательности. 
    4
  2. Длины максимальной возрастающей подпоследовательности, а потом в каждой строке по одному элементу 
    4
2
5
7
8