Préstamo de cantidades "generosas" de dinero

12

Introducción

Tienes un amigo que sigue pidiéndote préstamos y te estás cansando de ello. Hoy, volvió a pedir un préstamo. En lugar de rechazar su oferta, tienes una gran idea: trollea a tu amigo dándole tantas monedas / billetes como sea posible.

Desafío

Tomarás como entrada: la cantidad de dinero para la que tu amigo quiere un préstamo y la cantidad de monedas / billetes que tienes. Para este desafío, las denominaciones posibles son $ 20.00, $ 10.00, $ 5.00, $ 2.00, $ 1.00, $ 0.25, $ 0.10, $ 0.05 y $ 0.01. Un ejemplo de entrada es 5.67, [5, 3, 4, 5, 5, 9, 8, 1, 2]si su amigo quiere $ 5.67 y tiene 5 billetes de $ 20, 3 billetes de $ 10, etc. Su producción será la cantidad de monedas / billetes que le da a su amigo la mayor cantidad de metal / papel / plástico posible.

Si no es posible darle a su amigo la cantidad exacta de dinero que desea, dele la cantidad de dinero más cercana que pueda pagar que sea mayor de lo que él quiere. Por ejemplo, si tu amigo quiere $ 0.07 pero tú solo tienes [0, 0, 0, 0, 0, 2, 4, 2, 0], dale 2 monedas de $ 0.05 (¡no 1 $ 0.10 porque eso no le daría tantas monedas como sea posible!).

Si tu amigo quiere más dinero del que tú tienes, dale todo tu dinero (y reza para que no necesites comprar nada).

Casos de prueba

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]

Este es el por lo que gana el código más corto.

ericw31415
fuente
Tienes 2.00y 20.00pero no 0.2o 0.02:(
Mr. Xcoder
3
@ Mr.Xcoder muchos desafíos utiliza sistemas de divisas elegidos muy arbitrariamente. Es posible que deseemos hacer un meta para decidir si los desafíos relacionados con la moneda deberían determinar su propio sistema, tener un único sistema universal acordado, permitir el uso de varios sistemas o incluso hacer que todos estos desafíos también sean compatibles con el sistema como entrada, aunque eso podría dar lugar a síntomas de validación de entrada para algunos idiomas
Uriel
@ Mr.Xcoder ¿Quizás está pensando en billetes de dos dólares ? Estaba pensando en toonies.
ericw31415
¿Nuestras respuestas deben ejecutarse para todas las entradas, solo para las publicadas, o pueden funcionar para entradas pequeñas, pero fallar para la cuarta?
jrtapsell
@jrtapsell ¿La entrada 4 no debería causar problemas? 99 es generalmente un número lo suficientemente pequeño.
ericw31415

Respuestas:

1

Limpio , 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

Define la función @, tomando Realy [Int].

Pruébalo en línea!

Οurous
fuente
0

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]

Es bastante lento y cuesta memoria, así que solo pruebe casos pequeños

l4m2
fuente
0

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)

Embellecido

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

Prueba

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

El ejemplo 4 causa OutOfMemory, pero los otros 3 funcionan bien.

jrtapsell
fuente