a310. P-4-1少林寺的代幣 - 彰化精誠中學

內容

令狐沖去少林寺觀光，少林寺有四種代幣，面額分別是[1, 5, 10, 50]，令狐沖拿了n元去換代幣，請問以這四種代幣湊成n元，最少要多少枚代幣？

輸入說明

第一行是一個正整數m，代表有幾筆測資，以下有m行，每行是一筆測資，每筆測資是一個正整數n，n<1000。

輸出說明

依序每一行輸出每一筆測資的最少的代幣數量。

範例輸入 #1

範例輸出 #1

3
1
7

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (100%): 1.0s , <1K

提示：

21 = 10*2 + 1, 50 = 50*1, 123 = 50*2 + 10*2 + 1*3

標籤:

Greedy algorithm sweep-line

出處:

AP325 [管理者：

iris@stu.cch... (iris)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」