Preparing NOJ

硬币找钱问题

1000ms 65536K

Description:

设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins1:6]中,商店里各面值的硬币有足够多。在1 次购物中希望使用最少硬币个数。例如,1 次购物需要付款0.55 元,没有5 角的硬币,只好用2*20+10+5 4 枚硬币来付款。如果付出1 元,找回4 5 分,同样需要4 枚硬币。但是如果付出1.05 元(1 1元和1 5分),找回5 角,只需要3 枚硬币。这个方案用的硬币个数最少。

对于给定的各种面值的硬币个数和付款金额,编程计算使用硬币个数最少的交易方案。

Input:

每一行有6 个整数和1 个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。文件以6 0 结束。

Output:

结果应分行输出,每行一个数据。如果不可能完成交易,则输出”impossible”

Sample Input:

2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
0 0 0 0 0 0

Sample Output:

2
3

Note:

undefined

本题由旧版NOJ导入,来源:NUAA

Info

NOJ

Provider NOJ

Code NOJ1259

Tags

Submitted 5

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet