Задача №32. Монетки
Про порядок нарахування бонусних балів за ці задачі студентам ФОТІУС ЧНУ написано у відповідному документі на факультетському сервері.
В Волшебной стране используются монетки достоинством A1, A2,…, AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
Сначала вводится число N (1≤N≤109), затем — число M (1≤M≤15) и далее M попарно различных чисел A1, A2,…, AM (1≤Ai≤109).
Выведите сначала K — количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.
Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число –1 (минус один).
Оценка задачи
1 балл получат программы, правильно решающие задачу с дополнительными ограничениями Ai≤106, M≤10.
5 2 1 2
3 2 2 1
7 2 1 2
-1
5 2 3 4
0