pengantar

Anda memiliki teman yang terus meminta pinjaman dan Anda bosan karenanya. Hari ini, dia datang untuk pinjaman lagi. Alih-alih menolak tawarannya, Anda mendapatkan ide bagus: troll teman Anda dengan memberinya koin / tagihan sebanyak mungkin.

Tantangan

Anda akan menerima sebagai masukan: jumlah uang yang diinginkan teman Anda untuk pinjaman dan jumlah koin / tagihan yang Anda miliki. Untuk tantangan ini, denominasi yang mungkin adalah $ 20.00, $ 10.00, $ 5.00, $ 2.00, $ 1.00, $ 0.25, $ 0.10, $ 0.05, dan $ 0.01. Contoh input adalah 5.67, [5, 3, 4, 5, 5, 9, 8, 1, 2]jika teman Anda ingin $ 5,67 dan Anda memiliki 5 $ 20 tagihan, 3 $ 10 tagihan, dll. Output Anda akan menjadi jumlah koin / tagihan yang memberi teman Anda logam / kertas / plastik sebanyak mungkin.

Jika tidak mungkin memberi teman Anda jumlah uang yang tepat yang diinginkannya, berikan jumlah uang terdekat yang dapat Anda bayar yang lebih besar dari yang ia inginkan. Misalnya, jika teman Anda ingin $ 0,07 tetapi Anda hanya punya [0, 0, 0, 0, 0, 2, 4, 2, 0], berikan dia 2 $ 0,05 koin (bukan 1 $ 0,10 karena itu tidak akan memberinya koin sebanyak mungkin!).

Jika teman Anda menginginkan lebih banyak uang daripada yang Anda miliki, berikan dia semua uang Anda (dan berdoa Anda tidak perlu membeli apa pun).

Uji kasus

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]

Ini adalah kode-golf sehingga kode terpendek menang.

Bersih , 167 byte

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

Menentukan fungsi @, mengambil Realdan [Int].

Cobalah 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]

Ini sangat lambat dan biaya memori, jadi coba saja kasing kecil

Kotlin , 298 byte

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

Yg diperindahkan

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

Uji

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

Contoh 4 menyebabkan OutOfMemory, tetapi 3 lainnya berfungsi dengan baik.