# Introduction

You have a friend that keeps asking you for loans and you are getting tired of it. Today, he came for a loan again. Instead of turning down his offer, you get a great idea: troll your friend by giving him as many coins/bills as possible.

# Challenge

You will take as input: the amount of money your friend wants a loan for and the amount of coins/bills you have. For this challenge, the possible denominations are $20.00,$10.00, $5.00,$2.00, $1.00,$0.25, $0.10,$0.05, and $0.01. An example of input is 5.67, [5, 3, 4, 5, 5, 9, 8, 1, 2] if you friend wants$5.67 and you have 5 $20 bills, 3$10 bills, etc. Your output will be the amount of coins/bills that gives your friend as much metal/paper/plastic as possible.

If it is not possible to give your friend the exact amount of money he wants, give him the closest amount of money you can pay that is greater than what he wants. For example, if your friend wants $0.07 but you only have [0, 0, 0, 0, 0, 2, 4, 2, 0], give him 2$0.05 coins (not 1 \$0.10 because that wouldn't be giving him as many coins as possible!).

If your friend wants more money than you have, give him all your money (and pray you won't need to buy anything).

# Test cases

Input:  6.54, [9, 8, 7, 6, 5, 4, 3, 2, 4]
Output: [0, 0, 0, 1, 4, 1, 2, 1, 4]

Input:  2, [0, 1, 0, 0, 0, 0, 0, 0, 0]
Output: [0, 1, 0, 0, 0, 0, 0, 0, 0]

Input:  9999, [0, 0, 0, 0, 0, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 0, 0, 0, 1]

Input:  0, [99, 99, 99, 99, 99, 99, 99, 99, 99]
Output: [0, 0, 0, 0, 0, 0, 0, 0, 0]


This is so shortest code wins.

• You have 2.00 and 20.00 but no 0.2 or 0.02 :( Commented Dec 24, 2017 at 15:48
• @Mr.Xcoder many challenges uses very arbitrarily chosen currency systems. We might want to make a meta to decide whether currency related challenges should determine their own system, have a single universal system agreed upon, allow the usage of several systems or even make all this challenges to also support the system as input, although that might result in input-validation symptoms for some langauges Commented Dec 24, 2017 at 15:58
• @Mr.Xcoder Perhaps you're thinking of two-dollar bills? I was thinking toonies. Commented Dec 24, 2017 at 16:28
• Do our answers need to run for all inputs, just for the ones posted, or can they work for small inputs, but fail for the 4th one? Commented Dec 27, 2017 at 13:11
• @jrtapsell Input 4 shouldn't cause problems though? 99 is generally a small enough number. Commented Dec 27, 2017 at 14:19

# Clean, 167 bytes

import StdEnv
@n l#m=[p\\p<-[[if(y==u)(x-1)x\\x<-l&y<-[0..]]\\u<-[0..]&v<-l|v>0]|sum[a*b\\a<-[2000,1000,500,200,100,25,10,5,1]&b<-p]>=toInt(n*100.0)]
|m>[]= @n(hd m)=l


Defines the function @, taking Real and [Int].

Try it online!

# JavaScript, 213 Bytes

x=>y=>(F=(x,y,z,u=9)=>u--?[...Array(y[0]+1)].map((_,i)=>F(x-i*[1,5,10,25,100,200,500,1e3,2e3][u],y.slice(1),[...z,i],u))&&G:x>0||G.push([z,x-1/eval(z.join+1+)]),F(x*100,y,G=[]).sort((a,b)=>b[1]-a[1])[0]||[y])[0]


It's pretty slow and cost memory, so only try small cases

# Kotlin, 298 bytes

{t,c->with(c.fold(listOf(listOf<Int>())){o,x->o.flatMap{a->(0..x).map{a+it}}}.groupBy{it.zip(C).map{(a,b)->a*b}.sum()}.mapValues{(_,b)->b.maxBy{it.sum()}!!}.toSortedMap().asSequence()){firstOrNull{it.key==t}?:firstOrNull{it.key>t}?:last()}.value}
val C=listOf(20.0,10.0,5.0,2.0,1.0,0.25,.1,.05,.01)


## Beautified

        { t, c ->
with(c.fold(listOf(listOf<Int>())) { o, x ->
o.flatMap { a -> (0..x).map { a + it } } /* Get all of the options. */
}.groupBy { it.zip(C).map { (a, b) -> a * b }.sum() }
.mapValues { (_,b)->b.maxBy { it.sum() }!! }
.toSortedMap().asSequence()) {
firstOrNull { it.key == t } ?:
firstOrNull { it.key > t } ?:
last()
}.value
}
val C = listOf(20.0, 10.0, 5.0, 2.0, 1.0, 0.25, .1, .05, .01)


## Test

val calc: (target: Double, coins: List<Int>) -> List<Int> =
{t,c->with(c.fold(listOf(listOf<Int>())){o,x->o.flatMap{a->(0..x).map{a+it}}}.groupBy{it.zip(C).map{(a,b)->a*b}.sum()}.mapValues{(_,b)->b.maxBy{it.sum()}!!}.toSortedMap().asSequence()){firstOrNull{it.key==t}?:firstOrNull{it.key>t}?:last()}.value}
val C=listOf(20.0,10.0,5.0,2.0,1.0,0.25,.1,.05,.01)

data class Test(val target: Double, val input: List<Int>, val output: List<Int>)

val tests = listOf(
Test(2.0, listOf(0, 1, 0, 0, 0, 0, 0, 0, 0), listOf(0, 1, 0, 0, 0, 0, 0, 0, 0)),
Test(9999.0, listOf(0, 0, 0, 0, 0, 0, 0, 0, 1), listOf(0, 0, 0, 0, 0, 0, 0, 0, 1)),
Test(6.54, listOf(9, 8, 7, 6, 5, 4, 3, 2, 4), listOf(0, 0, 0, 1, 4, 1, 2, 1, 4)),
Test(0.0, listOf(99, 99, 99, 99, 99, 99, 99, 99, 99), listOf(0, 0, 0, 0, 0, 0, 0, 0, 0))
)

fun main(args: Array<String>) {
for (t in tests) {
if (t.output != calc(t.target, t.input)) {
throw AssertionError()
} else {
println("Passed")
}
}
}


Example 4 causes OutOfMemory, but the other 3 work well.