eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Монеты

Монеты

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Имеются монеты с разными фиксированными номиналами, выраженными в копейках (например, 3 и 5 копеек) в достаточном количестве. Написать программу COINS, которая:

  1. определяет, можно ли представить заданную сумму S (выраженную в копейках), пользуясь монетами заданных номиналов,

  2. если это возможно, то представляет эту сумму с помощью минимального количества монет.

Входные данные

Входной файл содержит в первой строке сумму S (0S1000000000), во второй строке - N - количество разных номиналов (1N20), а в следующих N строках - A_{1 }… A_{N } - номиналы (в порядке возрастания), которые можно использовать (0 < A_1 < A_2_{ }< ... < A_N1000000000).

Выходные данные

Выходной файл должен содержать в первой строке знак "+", если заданную сумму S можно представить, и знак "-", если нельзя. Если представление суммы существует, то следующие N строк должны содержать количества монет каждого номинала, которые нужны для представления суммы S с помощью минимального количества монет.

Пример

Входные данные #1
514
2
3
5
Выходные данные #1
+
3
101
Автор Сергей Данильченко
Источник X Всеукраинская олимпиада по информатике, 1997 г.