c317. 硬幣問題!前傳
Tags :
Accepted rate : 1021人/1147人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2018-01-08 18:29

Content

小明買了 X 元的商品,要付錢發現他只有兩種硬幣,幣值分別為 a 元和 b 元。

他希望用最少的硬幣湊到「剛好」X 元,請告訴小明最少需要用多少硬幣。

Input

第一行有一個整數 N (N <= 1,000),表示接下來會有 N 筆輸入

接下來 N 行,每一行有三個整數 X, a, b 表示小明要用 a, b 兩種幣值的硬幣湊出 X 元

(1000>= X >= a >= b >= 1)

Output

如果可以剛好湊到 X 元,請輸出最少需要的硬幣數量。

如果沒辦法剛好湊到,請輸出 -1。

Sample Input #1
3
258 24 20
144 11 3
309 24 9
Sample Output #1
-1
16
16
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint :

258 無法用 24 和 20 湊出 => 輸出 -1 
144 = 11 * 12 + 3 * 4 => 輸出 16(= 12+4)
309 = 24 * 11 + 9 * 5 => 輸出 16(= 11+5)

Tags:
出處:
[管理者: VacationClub (雄中公假社) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
20885 fire5386 (becaidorz) c317
解題想法
2354 2020-03-15 20:17
19533 qa5231677@gm ... (企鵝水晶) c317
1903 2019-10-08 21:39