HZNUOJ

贪心算法入入入入门题

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:532     AC:321     Score:100.00

Description

已知有面值为1元,2元,5元,10元,20元,50元,100元的七种纸币,小张想买一个价格为$x$元的玩具。小张是个土豪,假设他同时拥有这七种纸币,并且每一种都有无数张。问小张最少需要支付几张纸币可以刚好付清玩具的价格。

Input

一个整数$x$,代表玩具的价格。($1$<=$x$<=$1$,$000$,$000$,$000$)

Output

一个整数,表示最少要支付的纸币数量。(题目保证一定有解)

Samples

input
3
output
2

Hint

注意商家不会找零,比如小张总共使用了$n$张纸币,那么这$n$张纸币的面值总和必须要恰好等于玩具的价格。

题解:https://pasteme.cn/41783

Author

QIU, Longfeng