All submissions for this problem are available.
The Currency of some country has 'k' number of denominations. For each
denominaion , there is a coin .
Whenever a transaction happens with the shopkeeper, then to pay an amount 'X',
you give exactly or some amount greater than 'X' ( let us say 'Y' ) to the
shopkeeper. He then pays back the extra amount ( Y-X ) back to you. Both of
you try to minimize the number of coins exchanged in the process.
For example, if X = 68 and you have the denominations , 1,2,5,10,20,50 , then
the optimal transaction could be you paying the shopkeeper 50+20 units ( 2 coins
) and then the shopkeeper paying you back 2 units ( 1 coin ) . Hence , the total
number of coin exchanged in the process being 3 ( 50 + 20 - 2 ).
The efficiency of a set of denominations is calculated by the minimum number of
coin exchange required for every integer coin value between 1 and N ( some upper
bound, lets assume ) and taking their average as A. Lower the A, better is the
set of denomination.
Write a program that, given a series of coins, calculates the average and
maximum number of coins needed to pay any amount in the range [1,N]. You may
assume that both parties involved have sufficient numbers of any coin at their
The first line contains the number of test cases.
For each test case, there is a single line containing N ( 1<=N<=100 ),Number of
denominations K( K<=10 ) and then the value of each denomination ; all separated
by a single space.
For each test case the output is a single line containing first the average and
then the maximum number of coins involved in paying an amount in range [1,N]. The
average should be accurate upto 2 decimal places.
3 100 6 1 2 5 10 20 50 100 6 1 3 10 15 51 84 100 6 1 4 9 16 25 36
2.96 5 2.56 3 2.85 5
|Time Limit:||0.285714 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.