All submissions for this problem are available.
Sawan is a Shopkeeper. He has to deal with many customers in a day. Many times it happens that
he has only N types of notes of values(V1,V2,....Vn) left to give to the customer. He has a habit to
give minimum number of notes to the customers. Suppose a Customer buys his items for Rupees ‘X’ but he gives Rupees ’Y’ to the Shopkeeper Sawan. Now It is the job of Sawan to give customer back his remaining money (denoted by ‘S’) with minimum mumber of notes ‘N’.
Help Sawan to give the money to the Customer with minimum number of notes..
The first line contains a single integer T, the number of test cases. T test cases follow. Each testcase consists of a three lines.
First line contains the integer Y.
Second line contains the integer X.
Third line contains the integer N.
Fourth line contains N values of notes separated by space(V1,V2,....Vn).
For each test case, output a single line consisting of minimum number of notes given by Sawan to Customer.
- 1 <= T <= 10000
- 1 <= X < Y<= 100000
- 1 <= N <= 500
- 1 <= Vi <= 100
Input: 1 50 39 3 1 3 5 Output: 3
Sawan used two notes of 5 and one note of 1. Total=2+1=3 notes
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, RUBY, PHP, GO, SCALA, PERL, PIKE, BASH, LISP sbcl, LISP clisp, JS, ERL, PERL6|
Fetching successful submissions