题目描述

在一家十元商店里，所有商品的价格都不超过 $10$ 美元。为了在收银台更高效地服务顾客，需要以最少的硬币数量提供找零。

在这个问题中，你需要用不同的硬币组合出给定的找零金额。请编写一个程序，计算每种硬币所需的数量。

输入包括一个金额 $v$，硬币集合的大小 $n$，以及每种硬币的面值 $f_1, f_2, \dots, f_n$。输出是一个数列，即 $c_1, \dots, c_n$，表示每种硬币所需的数量。找零的方式可能有很多种。金额 $v$ 是一个满足 $0 < v \le 2000$ 的整数，代表所需的找零金额（以分为单位）。硬币的面值小于或等于 $10000$。你的程序应输出所需硬币总数最少的组合。

例如，由香港金融管理局发行的港币硬币包括 $10$ 分、$20$ 分、$50$ 分、$1$ 元、$2$ 元、$5$ 元和 $10$ 元，在输入中将表示为 $n = 7$，$f_1 = 10$，$f_2 = 20$，$f_3 = 50$，$f_4 = 100$，$f_5 = 200$，$f_6 = 500$，$f_7 = 1000$。

输入格式

输入可能包含多个测试用例，请处理到文件末尾。每个测试用例在一行中包含整数 $v, n, f_1, \dots, f_n$。保证 $n \le 10$ 且 $f_1 < f_2 < \dots < f_n$。

输出格式

输出为一行 $n$ 个整数，用空格分隔。如果不存在任何可行的找零方案，你的程序应输出单个 $-1$。如果存在多个可行方案，你的程序应输出使用了更多低面值硬币的那个方案。

2000 7 10 20 50 100 200 500 1000
250 4 10 20 125 150
35 4 10 20 125 150
48 4 1 8 16 20
40 4 1 10 13 37
43 5 1 2 21 40 80

0 0 0 0 0 0 2
0 0 2 0
-1
0 1 0 2  
3 0 0 1
1 1 0 1 0

提示

翻译由 DeepSeek V4 Pro 完成