n262. 我討厭零錢
Tags :
Accepted rate : 7人/9人 ( 78% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-03-01 14:04

Content

文文討厭口袋裡裝一堆重重的硬幣,也討厭皮夾裡放很多小面額的紙鈔讓它變得鼓鼓的。所以他在買東西時,都會儘量把皮夾和口袋裡的小面額錢幣儘量用掉。文文今天要留晚自習,正在學校附近買晚餐,給你文文現有的現金及晚餐的金額,請問文文要拿多少錢給老闆,才能讓找完錢以後他口袋及皮夾裡的錢幣數量越少越好?

新臺幣現行的發行幣值自 1981 年起使用,硬幣單位包括 0.5 元 (伍角)、1 元、5 元、10 元、20 元及 50 元,紙鈔單位有 100 元、200 元、500 元、1000 元、2000 元。但是 0.5、20、200、2000 這幾種面額的流通量較少,我們假設文文及老闆都完全沒有這些面額的錢幣。老闆則有充足的其它面額錢幣以供找零,也就是說,不會有像老闆沒有 50 元硬幣而找你 5 個 10 元硬幣這樣的事情發生。

因為文文一直保持著這個習慣,所以他身上面額 1, 10, 100 的錢幣永遠不會超過四個 (張)、面額 5, 50, 500 的錢幣不會超過一個 (張)。因此下次如果你需要把一張 500 元換成 5 張 100 元之類的需求,你就不用問他了,因為他身上永遠不會有超過 4 張的 100 元鈔票。

假設文文現在身上有 539 元,以他良好的習慣,這一定是 500×1 + 10×3 + 5×1 + 1×4 = 539。如果他的晚餐是 142 元,身上的硬幣 39 元不足以支付,那麼一定得用到那張 500 元紙鈔。可是如果他給老闆 500 元,老闆就會找他 100×3 + 50×1 + 5×1 + 1×3 = 358 元,這時候他身上就會有 100×3 + 50×1 + 10×3 + 5×2 + 1×7 = 397 元,一共有 3 + 1 + 3 + 2 + 7 = 16 個錢幣。

但是如果他給老闆 502 元,老闆找他 100×3 + 50×1 + 10×1 = 360 元,那麼他身上就會有 100×3 + 50×1 + 10×4 + 5×1 + 1×2 = 397 元,一樣的金額,但是錢幣的數量就只有 3 + 1 + 4 + 1 + 2 = 11 個。

Input

輸入只有一行,含有兩個整數 𝑛 及 𝑚 (0 < 𝑚 ≤ 𝑛 ≤ 10000),𝑛 為文文身上的現金,𝑚 為晚餐的金額。

Output

輸出一個整數,代表文文要給老闆的金額。

Sample Input #1
539 142
Sample Output #1
502
Sample Input #2
187 58
Sample Output #2
60
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint :
Tags:
出處:
板橋高中教學題 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」