introduction

Vous avez un ami qui ne cesse de vous demander des prêts et vous en avez assez. Aujourd'hui, il est revenu pour un prêt. Au lieu de refuser son offre, vous avez une bonne idée: troll votre ami en lui donnant autant de pièces / billets que possible.

Défi

Vous prendrez comme entrée: le montant d'argent que votre ami veut un prêt et le montant de pièces / billets que vous avez. Pour ce défi, les dénominations possibles sont de 20,00 $, 10,00 $, 5,00 $, 2,00 $, 1,00 $, 0,25 $, 0,10 $, 0,05 $ et 0,01 $. Un exemple d'entrée est 5.67, [5, 3, 4, 5, 5, 9, 8, 1, 2]si votre ami veut 5,67 $ et que vous avez 5 billets de 20 $, 3 billets de 10 $, etc. Votre sortie sera la quantité de pièces / billets qui donne à votre ami autant de métal / papier / plastique que possible.

S'il n'est pas possible de donner à votre ami le montant exact qu'il souhaite, donnez-lui le montant le plus proche que vous puissiez payer, supérieur à ce qu'il souhaite. Par exemple, si votre ami veut 0,07 $ mais que vous en avez seulement [0, 0, 0, 0, 0, 2, 4, 2, 0], donnez-lui 2 pièces de 0,05 $ (pas 1 $ 0,10 car cela ne lui donnerait pas autant de pièces que possible!).

Si votre ami veut plus d'argent que vous, donnez-lui tout votre argent (et priez pour que vous n'ayez rien à acheter).

Cas de test

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]

C'est le code-golf donc le code le plus court gagne.

Nettoyer , 167 octets

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

Définit la fonction @, en prenant Realet [Int].

Essayez-le en ligne!

JavaScript, 213 octets

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]

C'est une mémoire assez lente et coûteuse, alors n'essayez que de petits cas

Kotlin , 298 octets

{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)

Embellie

        { 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)

Tester

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")
        }
    }
}

L'exemple 4 provoque OutOfMemory, mais les 3 autres fonctionnent bien.