回分類題庫
b034: 悠閒的超商店員
關鍵字: 貪婪演算法-零錢問題

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 1197 Times / 1078 Users | Submit : 1808 Times / 1109 Users | Accepted rate : 97%
題目加入時間 : 2011-11-02 08:49

Content: 简体中文

還記得「忙碌的超商店員」這個題目嗎?現在場景換到另一個國家,這個國家的貨幣有1、5、10、50、100、500、1000、5000、10000元等9種,而超商同樣要求店員找給顧客的錢的個數必須是最少的,你能幫他完成這項工作嗎?

Input:

輸入一個正整數 N (1<=N<=100000),代表要找的錢。

Output:

請輸出找給顧客 N 元時,最少的錢的個數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入1:
17

輸入2:
99

Sample Output :

輸出1:
4

輸出2:
10

Hint :

Author :

貪婪演算法-零錢問題 (管理員:sagit)

  Solve it!   Status Forum