设有 6 种不同面值的硬币,各硬币的面值分别为 5 分,1 角,2 角,5 角,1 元,2 元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins[1:6]中,商店里各面值的硬币有足够多。在 1 次购物中希望使用最少硬币个数。
例如,1 次购物需要付款 0.55 元,没有 5 角的硬币,只好用 2*20+10+5 共 4 枚硬币来付款。如果付出 1 元,找回 4 角 5 分,同样需要 4 枚硬币。但是如果付出 1.05 元(1 枚 1元和 1 枚 5 分),找回 5 角,只需要 3 枚硬币。这个方案用的硬币个数最少。
对于给定的各种面值的硬币个数和付款金额,计算使用硬币个数最少的交易方案。
输入数据每一行有 6 个整数和 1 个有 2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。文件以 6 个 0 结束。
将计算出的最少硬币个数输出。结果应分行输出,每行一个数据。如果不可能完成交易,则输出“impossible” 。
2 4 2 2 1 0 0.95 2 4 2 0 1 0 0.55 0 0 0 0 0 0
2 3