Golfme un poco de efectivo del cajero automático

26

La tarea es simple. Conseguirme algunos 1000, 500y 100notas.

Cómo ? usted puede preguntar No se preocupe, no necesita robar un banco, ya que hay un cajero automático cerca que acepta su tarjeta de crédito. Pero su límite de crédito es suficiente para la tarea, por lo que debe tener cuidado con los retiros.

Reto

Dado el número de 1000, 500y 100notas requeridas, el cálculo de los retiros específicos necesarios para conseguir por lo menos esas muchas notas. En cada retiro, el cajero automático puede escupir cada una de las notas según las siguientes reglas:

  • La cantidad retirada ( A) es menor que5000
    • Si A%1000 == 0, entonces ATM escupe 1 500nota, 5 100notas y 1000notas de descanso
    • De lo contrario A%500 == 0, si el cajero automático escupe 5 100notas, descansa 1000notas
    • Si no A%1000 < 500, el cajero automático escupe floor(A/1000) 1000notas y 100notas de descanso
    • De lo contrario A%1000 > 500, si el cajero automático escupe floor(A/1000) 1000notas, 1 500y 100notas de descanso
  • La cantidad retirada es mayor que igual a 5000
    • Si A%1000 == 0, entonces el cajero automático escupe 2 500notas y 1000notas de descanso
    • De lo contrario, si A%500 == 0el cajero automático escupe 1 500nota y descansa 1000notas
    • Si no A%1000 < 500, el cajero automático escupe floor(A/1000) 1000notas y 100notas de descanso
    • De lo contrario A%1000 > 500, si el cajero automático escupe floor(A/1000) 1000notas, 1 500y 100notas de descanso

Para aclarar, aquí hay una tabla completa de notas retiradas para todas las cantidades posibles hasta 7000(puede retirar más, pero el patrón no cambia después). El orden es <1000> <500> <100>:

 100 => 0 0 1                  2500 => 2 0 5                   4800 => 4 1 3
 200 => 0 0 2                  2600 => 2 1 1                   4900 => 4 1 4
 300 => 0 0 3                  2700 => 2 1 2                   5000 => 4 2 0
 400 => 0 0 4                  2800 => 2 1 3                   5100 => 5 0 1
 500 => 0 0 5                  2900 => 2 1 4                   5200 => 5 0 2
 600 => 0 1 1                  3000 => 2 1 5                   5300 => 5 0 3
 700 => 0 1 2                  3100 => 3 0 1                   5400 => 5 0 4
 800 => 0 1 3                  3200 => 3 0 2                   5500 => 5 1 0
 900 => 0 1 4                  3300 => 3 0 3                   5600 => 5 1 1
1000 => 0 1 5                  3400 => 3 0 4                   5700 => 5 1 2
1100 => 1 0 1                  3500 => 3 0 5                   5800 => 5 1 3
1200 => 1 0 2                  3600 => 3 1 1                   5900 => 5 1 4
1300 => 1 0 3                  3700 => 3 1 2                   6000 => 5 2 0
1400 => 1 0 4                  3800 => 3 1 3                   6100 => 6 0 1
1500 => 1 0 5                  3900 => 3 1 4                   6200 => 6 0 2
1600 => 1 1 1                  4000 => 3 1 5                   6300 => 6 0 3
1700 => 1 1 2                  4100 => 4 0 1                   6400 => 6 0 4
1800 => 1 1 3                  4200 => 4 0 2                   6500 => 6 1 0
1900 => 1 1 4                  4300 => 4 0 3                   6600 => 6 1 1
2000 => 1 1 5                  4400 => 4 0 4                   6700 => 6 1 2
2100 => 2 0 1                  4500 => 4 0 5                   6800 => 6 1 3
2200 => 2 0 2                  4600 => 4 1 1                   6900 => 6 1 4
2300 => 2 0 3                  4700 => 4 1 2                   7000 => 6 2 0
2400 => 2 0 4

Lista proporcionada por Martin

La captura

Dado que el límite de crédito en su tarjeta de crédito es suficiente, debe asegurarse de que monto total retirado en los retiros sea el mínimo posible para la entrada / requisito de notas dado.

Entrada

La entrada puede estar en cualquier formato favorable para tres números correspondientes al número de notas requeridas de valor 1000, 500y100 . No necesariamente en ese orden.

Salida

La salida es la cantidad que se retirará en cada transacción separada por una nueva línea.

Ejemplos

Entrada (formato <1000> <500> <100>):

3 4 1

Salida:

600
600
600
3600

un poco mas:

7 2 5
5000
3500

1 2 3
600
1700

21 14 2
600
600
600
1600
5000
5000
5000
5000
5000

Supuestos

  • Puede suponer que el cajero automático tiene un número infinito de billetes de cada cantidad.
  • También puede suponer que puede realizar cualquier cantidad de transacciones.
  • Además, la solución a algunos valores de entrada puede no ser única, por lo que puede generar 1 de la solución que cumpla con la cantidad mínima posible y las condiciones mínimas requeridas para las notas.

Como de costumbre, puede escribir una entrada de lectura completa del programa a través de STDIN / ARGV e imprimir la salida a STDOUT o una función que toma la entrada a través de argumentos y devuelve una lista de enteros correspondiente a las cantidades o una cadena con cantidades separadas por una nueva línea.

Este es el código de golf, por lo que el código más corto en bytes gana.

code-golf combinatorics Optimizador
fuente
@nutki de hecho. Editado
Optimizador
¿Hay alguna restricción de velocidad? ¿Debería 21 14 2terminar el último caso de prueba en un tiempo razonable?
Jakube
1
@Jakube En un tiempo razonable, sí (digamos menos de 5-6 horas). Pero como tal, no hay límite, ya que este es el código de golf.
Optimizador
Entonces, si retiro 0, ¿me dará cinco 100 notas?
AJMansfield
@AJMansfield, por supuesto que no. No puede retirar la cantidad 0
Optimizer

Respuestas:

7

JavaScript, 184 148

function g(a,b,c){x=[];while(a>0||b>0||c>0){i=b<3||a<4?a:4;a-=i;if(i>3&&b>1){b-=2;i++}else{i+=(c--<b&&i>4?0:.1)+(b-->0?.5:0)}x.push(i*1e3)}return x}

http://jsfiddle.net/vuyv4r0p/2/

devuelve una lista de enteros correspondientes a los montos de retiro

hoffmale
fuente
Tratar g(5,1,1). Una solución mejor: 5600.
jimmy23013
debe ser resuelto ahora
hoffmale
g(5,1,0), Solución: 5500.
jimmy23013
que debe ahora también se puede fijar ^^ gracias por señalarlo, debo ser demasiado sueño
hoffmale
g(5,2,0), Solución: 6000.
jimmy23013
1

Perl 5: 223

Editar

Esta solución se realizó con una suposición errónea de que 7K es el límite del cajero automático. En realidad, esto hizo que la tarea fuera más interesante, ya que requería una programación dinámica (el patrón de movimiento era bastante regular, pero codificarlo probablemente sería más largo que calcularlo en vivo como lo hice yo). Con cualquier cantidad posible, el patrón de movimiento es tan regular que es trivial codificarlo. No sé si la solución de @hoffmale ahora es correcta, pero estará entre estas líneas. Lamentablemente, será otra tarea en la que primero alguien viene con una solución y luego es trasladado a un idioma de golf para ganar.

Un poco más lento que la solución original (pero aún por debajo de los segundos para los parámetros por debajo de 100).

#!perl -pa
$c{0,0}=$f=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/.(?=.$)/>($n=$c{$i-$`,$j-$'})||${$r=\$c{$i,$j}}<($x=$n+$&)&&$$r
or$f=$$r="$x $n".($'.$&+5*$`)."00
"for 204..206,105,106,11..15,110..114}}$_=$f."100
"x($c-$f+3);s/.*\b3//

Solución más rápida 259.

#!perl -pa
$c{0,0}=($a,$b,$c)=@F;for$i(0..$b){for$j(0..$a){
/\B./<($%=$c{$i-$&,$j-$'}+$`)&&(!${$r=\$c{$i,$j}}||$$r>$%)and$d{$i,$j}=$_,$$r=$%for
qw/024 025 026 015 016/,101..105,110..114}}
$d{$b,$a}=~/\B./,$c-=$`,$b-=$&,$a-=$',print$'.$`+5*$&,"00
"while$a+$b;$_="100
"x$c

Utiliza STDIN:

$perl atm.pl <<<"21 14 2"
5000
5000
5000
5000
5000
600
600
600
1600
nutki
fuente
Tratar 10 0 0. Solución mejor: 10100.
jimmy23013
@ user23013 oops, no entendí la pregunta. Supuse que 7k es la cantidad máxima :( Espero poder arreglarlo.
nutki