Problem1019--硬币问题

1019: 硬币问题

[Creator : ]
Time Limit : 1 sec  Memory Limit : 128 MB

Solved: 33Submit: 53Statistics

Description

有1元，5元，10元，50元，100元，500元的硬币各C1，C5，C10，C50，C100，C500枚。现在要用这些硬币来支付A元，最少需要多少枚硬币？假定本题至少存在一种支付方法。
限制条件0<=C1,C5,C10,C50,C100,C500<=10^9，0<=A<=10^9

Input

有多组测试数据，每组测试数据第一行输入A，表示要支付的钱，第二行有六个数为C1，C5，C10，C50，C100，C500。

Output

输出最少需要的硬币数

Sample Input Copy 

620
3 2 1 3 0 2

Sample Output Copy 

6

Source/Category

 贪心算法 
Submit