70. TBA's Coins

0 Judge

Code: 0


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