All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There is a bank which provides coins of various denominations of euros. In particular, it provides you coins of value 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000 euros.
Today, Chef went to market with a coin of C euros, i.e. the coin with value C is among one of the above given 15 coins. Chef wanted to buy a brand new laptop worth L euros from a shop. Sadly the shop owner had just opened the shop and did not had any change. So he wanted the exact amount of money, no less, no more. Chef was forced to visit the nearby bank to obtain the desired change.
In the bank, Chef can ask for a change of some part of the amount C, and deposit the remaining money in his account. Bank will give him change in the coins of above given denominations.
Chef does not want to deposit a lot of amount in his account, as he believes in having as much cash in hand as possible. So, he wants to ask the bank for a change of as large amount as possible, such that it is possible to pay the L euros for the laptop. As Chef does not know what particular types of coins the bank will provide him in the change, he wants to make sure that with any type of coins bank might provide, he should be able to pay the laptop cost.
For example, let Chef has initially 5 euros. The laptop cost is 1 euro.
- If he asks bank to directly provide change for 5 euros, bank might provide him a coin of 5 euros, which he can't use to pay 1 euro.
- If he asks bank to provide change for 4 euros, with bank depositing remaining 1 euro in his account, bank might provide him 2 coins of 2 euros each, which still he can't use to pay 1 euro.
- If he asks bank to provide change for 3 euros, with bank depositing remaining 2 euros in his account, bank can give him either one coin of 1 euro and another coin of 2 euros, or three coins of 1 euro each. In both of these scenarios, Chef can use the 1 euro coin to pay for the laptop.
So, Chef will need to ask for a change of maximum 3 euros to ensure that he is able to pay for the laptop.
You can notice that Chef can directly ask the Bank to give him a change of L euros. But, in this way, bank will deposit C - L euros in his account. There might be a way of paying the laptop while getting a change of larger amount from the bank, thus depositing less amount in his bank balance.
First line of the input contains a single integer T denoting the number of test cases.
For each test case, there will be a single line containing two space separated integers C, L, denoting the value of coin Chef carries and the cost of laptop, respectively.
For each test case, output a single integer corresponding to the maximum amount of money for which the Chef should ask the bank to provide the change so that he is able to pay for the laptop.
- 1 ≤ T ≤ 88888
- C is among one of the above mentioned 15 denominations, i.e. (1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000).
- 1 ≤ L ≤ C
Input 2 5 1 50000 1 Output: 3 3
Example case 1. It is already explained in the problem statement.
|Tags||cook70, dynamic-programming, medium-hard, recursion, wwwwodddd|
|Time Limit:||5 sec|
|Source Limit:||20000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.