ZOJ Problem Set - 3912
Darksun loves traveling very much, especially when there are many delicious snacks in the place where he travels. Darksun is not wealthy but he is very clever. In oder to taste more kinds of yummy snacks with limited money, Darksun used many ways to save money such as taking bus and taking underground. As a result, he always pays attention to collecting coins during the trip because coins are necessary when taking bus or underground.
However, during his last trip in Japan, he received an urgent phone call from ZJU, telling him to go back and attend the ACM training. He felt very sad when hearing the message. The saddest part was that he had collected thousands of coins which were extremely heavy. In order to carry fewer coins when boarding the plane, clever Darksun decided to use as many coins as possible to buy a nice Garage Kits(GK) because he loves Japanese cartoons so much.
There are only 6 kinds of coins, which are 1, 5, 10, 50 and 100. Now, we know that Darksun has a $1 coins, b $5 coins, c $10 coins, d $50 coins, e $100 coins and f $500 coins.
The GK that Darksun wanted to buy costs $p. It is ok for Darksun to give more money than $p to the cashier. If Darksun gives $q (q > p) to the cashier, the cashier will return $(q-p) using the fewest number of coins. For example, if q=100 and p=91 the cashier will give Darksun one $5 coin and four $1 coins.
Notice: However, it is invalid when any partial sum of the coins that Darksun gives to the cashier is equal to one of the coins' value that the cashier returns to him.
Now, please help Darksun to calculate the minimum number of coins he will have after buying the GK.
There are multiple cases. The first line of input is an integer T (T ≤ 10) which indicates the cases of test data.
For each case, please output one line, the minimum number of coins that Darksun has to carry when boarding the plane.
2 10 10 1 1 0 0 0 90 80 3 3 3 3 0
Author: ZHAO, Yueqi
Source: ZOJ Monthly, October 2015