Wprowadzenie

Masz przyjaciela, który ciągle prosi cię o pożyczki i masz już tego dość. Dziś znów przyszedł po pożyczkę. Zamiast odrzucić jego ofertę, masz świetny pomysł: trolluj swojego przyjaciela, dając mu jak najwięcej monet / rachunków.

Wyzwanie

Weźmiesz jako dane wejściowe: kwotę pieniędzy, na którą przyjaciel chce pożyczki, oraz liczbę posiadanych monet / rachunków. W przypadku tego wyzwania możliwe nominały to 20,00 USD, 10,00 USD, 5,00 USD, 2,00 USD, 1,00 USD, 0,25 USD, 0,10 USD, 0,05 USD i 0,01 USD. Przykładem wkładu jest, 5.67, [5, 3, 4, 5, 5, 9, 8, 1, 2]jeśli twój przyjaciel chce 5,67 $ i masz 5 banknotów 20 $, 3 rachunki 10 $ itp. Twój wynik wyniesie tyle monet / rachunków, które dadzą Twojemu przyjacielowi jak najwięcej metalu / papieru / plastiku.

Jeśli nie jest możliwe podanie przyjacielowi dokładnie takiej kwoty, jakiej chce, daj mu najbliższą kwotę, jaką możesz zapłacić, większą niż to, czego on chce. Na przykład, jeśli twój przyjaciel chce 0,07 $, a ty masz tylko [0, 0, 0, 0, 0, 2, 4, 2, 0], daj mu 2 monety 0,05 $ (nie 1 0,10 $, ponieważ nie dałoby mu to jak największej liczby monet!).

Jeśli twój przyjaciel chce więcej pieniędzy niż ty, daj mu wszystkie pieniądze (i módl się, abyś nie musiał niczego kupować).

Przypadki testowe

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]

To jest golf golfowy, więc wygrywa najkrótszy kod.

Czysty , 167 bajtów

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

Definiuje funkcję @, biorąc Reali [Int].

Wypróbuj online!

JavaScript, 213 bajtów

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]

Jest to dość powolna i kosztowna pamięć, więc wypróbuj tylko małe skrzynki

Kotlin , 298 bajtów

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

Upiększony

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

Przykład 4 powoduje OutOfMemory, ale pozostałe 3 działają dobrze.