TBA's Coins
題目敘述:
- 在OOXX國,他們的貨幣面值有1, 16, 32, 160, 320, 1600, 3200, 16000, 48000。
一個禮拜總共有$Q$天,TBA每天早上會去超商買早餐,當天他能額外使用一種折價券(價值為$A_i$)。
這個國家的超商十分地奇特,當你付錢時,店員只願意接受最少的(硬幣+折價券)數量,且支付金額要剛好為你所購買的商品價格。
每次消費TBA所能使用的折價券及硬幣數量都是無限的。
請問TBA在第$i$天購買價格為$B_i$物品時,最少要支付多少(硬幣+折價券)數量?
輸入:
- 第一行有一個數字$Q$,表示總天數($1\leq Q\leq100$)
- 接著有$Q$行,每行有兩個數字$A_i$、$B_i$。($1 \leq A_i, B_i \leq 2304000000 $)
輸出:
- 第$i$行輸出第$i$天TBA最少要支付多少的(硬幣+折價券)數量。
條件限制:
小測資(10%):
- 48000 | $A_i$ (表示$A_i$被$48000$整除)
- ($1 \leq B_i \leq 2304000000$)
中測資(40%):
- $48000 \leq A_i \leq 2304000000$
- ($1 \leq B_i \leq 2304000000$)
大測資(50%):
範例輸入:
請注意範例輸入最後一行後面是有換行符號的。
3
500 1000
3 18
1000 1000
範例輸出:
請注意範例輸出最後一行後面是有換行符號的。
2
3
1
測資說明:
- 第一筆測資: 1000 = 500 + 500
- 第二筆測資: 18 = 16 + 1 + 1
- 第三筆測資: 1000 = 1000
Hint:
2304000000 = 48000 * 48000
Judge Setting
run-time limit: 1600 ms
memory limit: 1048576 byte
測資數量: 10