|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 14-1. Монетки
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 1 секунда |
В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
Формат входных данных
Во входном файле записано сначала число N (1 <= N <= 109),
затем - число M (1 <= M <= 15) и далее M попарно различных
чисел A1, A2,..., AM (1 <= Ai <= 109).
Формат выходных данных
В выходной файл выведите сначала K - количество монет, которое
придется отдать Волшебному человечку, если он сможет заплатить
указанную сумму без сдачи. Далее выведите K чисел, задающих
достоинства монет. Если решений несколько, выведите вариант, в
котором Волшебный человек отдаст наименьшее возможное количество
монет. Если таких вариантов несколько, выведите любой из них.
Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
Пример
| input.txt | output.txt |
5 2 1 2 |
3 1 2 2 |
7 2 1 2 |
-1 |
5 2 3 4 |
0 |