1412: 最少钱币数

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

    用给定的几种钱币凑成某个钱数。例如:给定了6种钱币面值为2、5、10、20、50、100,用来凑15元,可以用5个2元、1个5元,或者1个5元、1个10元,等等。显然,最少需要2个钱币才能凑成15元。

    你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。

输入格式

    输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M(1 ≤ M ≤ 2000,整数),接着的一行中,第一个整数K(1 ≤ K ≤ 10)表示币种个数,随后是K个互不相同的钱币面值Ki(1 ≤ Ki ≤ 1000)。输入M=0时结束。

输出格式

    每个测试用例输出一行,及凑成钱数值M最少需要的钱币个数。如果凑钱失败,输出“Impossible”。你可以假设,每种待凑钱币的数量是无限多的。

输入样例 复制

15
6 2 5 10 20 50 100
1
1 2
0

输出样例 复制

2
Impossible

分类标签