Банкомат
Время на тест - 30 секунд.
В некотором государстве в обращении находятся банкноты определенных номиналов. Национальный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Национальному банку решить эту задачу.
Формат входных данных
Первая строка входных данных содержит натуральное число n, 0<n<=100. Вторая строка входных данных содержит n различных натуральных чисел x1, x2, ..., xn, не превосходящих 1.000.000. Третья строчка содержит натуральное число S, не превосходящее 5.000.000.
Формат выходных данных
Программа должна найти представление числа S в виде суммы слагаемых из множества {xi}, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести слово impossible.
Пример
Входные данные
5 1 3 7 12 32 40
Выходные данные
1 7 32
Входные данные
5 10 50 100 500 1000 99
Выходные данные
impossible
Теги:
данные,
вывести,
должна,
содержит,
число,
Формат,
данных,
числа,
банкнот,
программа,
impossible,
строка,
чисел,
существует,
строчка,
Третья,
Программа,
суммы,
слово,
Пример,
несколько,
последовательности,
множества,
экран,
найти,
решить,
номиналов,
хочет,
чтобы,
банкомат,
банкноты,
находятся,
секунд,
некотором,
государстве
Комментарии:
Нету комментариев для вывода...