Cortar la cadena de oro

32

Un viajero debe permanecer durante n días en un hotel fuera de la ciudad. No tiene efectivo y su tarjeta de crédito está vencida. Pero tiene una cadena de oro con n eslabones.

La regla en este hotel es que los residentes deben pagar el alquiler todas las mañanas. El viajero llega a un acuerdo con el gerente para pagar un eslabón de la cadena de oro por cada día. Pero el gerente también exige que el viajero haga el menor daño posible a la cadena mientras paga todos los días. En otras palabras, tiene que encontrar una solución para cortar la menor cantidad de enlaces posible.

Cortar un enlace crea tres subcadenas: una que contiene solo el enlace cortado y una a cada lado. Por ejemplo, cortar el tercer eslabón de una cadena de longitud 8 crea subcadenas de longitud [2, 1, 5]. El gerente se complace en hacer cambios, por lo que el viajero puede pagar el primer día con la cadena de longitud 1, luego el segundo día con la cadena de longitud 2, recuperando la primera cadena.

Su código debe ingresar la longitud n , y generar una lista de enlaces para cortar de longitud mínima.

reglas :

  • norte es un entero> 0.
  • Puede utilizar la indexación basada en 0 o en 1 para los enlaces.
  • Para algunos números, la solución no es única. Por ejemplo, si n = 15ambos [3, 8]y[4, 8] son salidas válidas.
  • Puede devolver la lista o imprimirla con cualquier separador razonable.
  • Este es el , por lo que gana el código más corto en bytes.

Casos de prueba :

Input          Output (1-indexed)
1              []
3              [1]
7              [3]
15             [3, 8]
149            [6, 17, 38, 79]

Ejemplo detallado

Para n = 15, cortar los enlaces 3 y 8 da como resultado subcadenas de longitud [2, 1, 4, 1, 7]. Esta es una solución válida porque:

 1 = 1
 2 = 2
 3 = 1+2
 4 = 4
 5 = 1+4
 6 = 2+4
 7 = 7
 8 = 1+7
 9 = 2+7
10 = 1+2+7
11 = 4+7
12 = 1+4+7
13 = 2+4+7
14 = 1+2+4+7
15 = 1+1+2+4+7

No existe una solución con un solo corte, por lo que esta es una solución óptima.

Apéndice

Tenga en cuenta que este problema está relacionado con la partición de enteros. Estamos buscando una partición P de n tal que todos los enteros del 1 al n tengan al menos una patición que sea un subconjunto de P .

Aquí hay un video de YouTube sobre un posible algoritmo para este problema.

polfosol ఠ_ఠ
fuente
No entiendo su referencia de "hacer cambios". En su ejemplo publicado, el segundo día paga con la cadena de 2 enlaces (y obtiene la cadena de 1 enlace (que pagó el día anterior) como cambio, según su explicación). Pero al tercer día, pagas con 1+2. ¿De dónde vino la segunda cadena de 2 eslabones?
Flater
44
@Flater El gerente ya lo tiene. Solo pagamos el adicional. De hecho, los RHS son los enlaces que el gerente posee cada día
polfosol ఠ_ఠ

Respuestas:

15

05AB1E , 23 11 8 bytes

ΔÍN-;иg=

Pruébalo en línea!

Utiliza indexación basada en 0.

Explicación:

             # start from the implicit input
Δ            # loop forever
 Í           # subtract 2
  N-         # subtract the current iteration number
    ;        # divide by 2
     и       # create a list of length x
      g      # get the length of the list
       =     # print

иgparece un noop, pero en realidad hace dos cosas útiles: se trunca a un número entero ( ;devuelve un flotante) y bloquea el intérprete si x es negativo (esta es la única condición de salida).


La solución de 23 bytes utilizó un enfoque muy diferente, así que aquí está para la posteridad: ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O( TIO , explicación ).

Mugriento
fuente
2
He borrado mi respuesta. El mío de 42 años y el tuyo de 11 es una gran diferencia para que no me sienta avergonzado, jaja. ;) Buena respuesta, y jajaja en el Ø.Ø. ¿Intentaste algunas cosas al azar para hacer un piso y asignar todos los negativos -1? De todos modos, muy buena respuesta y mucho más corta de lo que esperaba. Estaba pensando en unos 20 bytes después de publicar mi mala 42 byter.
Kevin Cruijssen
2
@KevinCruijssen Nnope, en Ø.Ørealidad fue mi primera idea. Su comentario me inspiró para probar cosas al azar: me encontré ®Ÿà, ï®My lo más importante, иgque los rendimientos de este bonito 8-byter. Siempre me pareció molesto que osabie prefiera no hacer nada en lugar de estrellarse en muchos casos (div por 0, tipo incorrecto, etc.), por lo que este bloqueo será útil.
Grimmy
2
Jeje, se supone que 05AB1E nunca se bloquea, pero tienes razón en que a veces es un poco molesto que nunca lo haga ... En el legado, ni siquiera sabría cómo bloquear, y en el pasado incluso tuvimos una división explícita por error cero que podríamos llamar manualmente. xD En la nueva versión, todavía se bloquea con un error con bastante frecuencia cuando se dan argumentos incorrectos a ciertos componentes incorporados. Y agradable -3 nuevamente.
Kevin Cruijssen
2
"bloquea el intérprete si x es negativo (esta es la única condición de salida)". - Me encanta eso
John Dvorak
9

Python 2 , 75 bytes

f=lambda n,i=0:n>=i<<i and f(n,i+1)or[min(n,2**j*i-i+j)for j in range(1,i)]

Pruébalo en línea!


Explicación:

Crea una secuencia de fragmentos 'binarios', con un número base que coincide con el número de cortes.

P.ej:

63 Se puede hacer en 3 cortes, lo que significa una partición en base-4 (ya que tenemos 3 anillos individuales):

Cortes:, 5, 14, 31que da cadenas de 4 1 8 1 16 1 32(ordenados:1 1 1 4 8 16 32 .

Todos los números se pueden hacer:

1       1
2       1 1
3       1 1 1
4       4
...
42      1 1 8 32
...
62      1 1 4 8 16 32
63      1 1 1 4 8 16 32

Otros ejemplos:

18: 4,11        ->  3 1 6 1 7
27: 5,14,27     ->  4 1 8 1 13 1
36: 5,14,31     ->  4 1 8 1 16 1 5
86: 6,17,38,79  ->  5 1 10 1 20 1 40 1 7
TFeld
fuente
1
¿No deberías agregar f=al comienzo? Dado que usa una llamada a fen la función lambda, y solo puedo suponer que se refiere al mismo lambda que está definiendo.
randomdude999
@ randomdude999, sí, lo olvidé ...
TFeld
@ randomdude999 ¿esa regla se aplica a todos los idiomas, o solo a python? Porque veo una respuesta de JavaScript que es una lambda pura en este desafío ...
Sombra
3
@Shadow Se aplica a todos los idiomas, pero solo para lambdas recursivas.
TFeld
1
@Sombra Una regla más genérica es que no puede hacer referencia a algo que no está definido en su código ni globalmente en su idioma, a menos que el desafío lo permita explícitamente. El caso más común es una función recursiva, pero esto se aplica a otras situaciones. Esta respuesta es otro ejemplo: fno es recursiva, pero se hace referencia en el código y, por lo tanto, debe nombrarse.
Arnauld
8

R , 77 69 bytes

-8 bytes gracias a Aaron Hayman

pmin(n<-scan(),0:(k=sum((a=2:n)*2^a<=n))+cumsum((k+2)*2^(0:k))+1)[-n]

Pruébalo en línea!

kk(k+1)2knorte1,1,...,1k(k+1),2(k+1),4 4(k+1),8(k+1),...,(k+1)2k-1

(Es posible que sea necesario acortar la última subcadena si superamos la longitud total de la cadena).

Sin golf (basado en una versión anterior similar):

n = scan()                            # read input
if(n - 1){                            # If n==1, return NULL
  k = match(F, (a = 2:n) * 2 ^ a > n) # compute k
  b = (k + 1) * 2 ^ (1:k - 1)         # lengths of subchains
  c = 1:k + cumsum(b)                 # positions of cuts
  pmin(c, n )                         # if last value is >n, coerce it to n
}

kkkk+12k+12k+24 4k+4 4k(k+1)2k-1.)

Si una(k) es el entero más pequeño norte requiriendo k cortes, entonces una(k)es OEIS A134401 .

Robin Ryder
fuente
Dudo que ayude con el caso especial n=1, pero una forma alternativa de generar los puntos de corte es la recurrencia 1, 4, 4a(n-1)-4a(n-2).
Peter Taylor
@ PeterTaylor Tuve una recurrencia similar para la informática k; esto corresponde a OEIS A134401: oeis.org/A134401 Pero mi implementación de la relación de recurrencia ocupa más bytes que el código actual.
Robin Ryder
Un poco de reorganización lo reduje a 73. ¡ Pruébelo en línea!
Aaron Hayman
@AaronHayman ¡Gracias! Movimiento inteligente usando en sumlugar de match.
Robin Ryder
69 bytes y eliminé eso si la declaración que te estaba molestando: ¡ Pruébalo en línea!
Aaron Hayman
3

Jalea , 12 bytes

’_‘ɼ:2»-µƬṖḊ

Pruébalo en línea!

Traducción de la respuesta 05AB1E de Grimy, ¡ así que asegúrese de votar esa también! Ligeramente decepcionado, esto viene en un byte más largo, ¡pero al menos tiene algo parecido a un emoticón como los primeros tres bytes!

Nick Kennedy
fuente
2

C ++, 109 , 107 bytes

-2 bytes gracias a Kevin

#include<iostream>
main(){int n,k=0;for(std::cin>>n;++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)std::cout<<n<<',';}

El algoritmo es similar a la respuesta de Robin Ryder. El código está escrito en una forma completa compilable. ¡Intentalo!

Detalles:

std::cin>>n;               // get the value of n as input
while(++k<<k<n);           // determine k
for(n-=k;n>0;k*=2,n-=k+1)  // we don't need n, so the lengths...
    std::cout<<n<<' ';     // of links are subtracted repeatedly

Esto tiene una variación de C con la misma longitud de bytes (no parece necesitar una respuesta por separado):

#include<stdio.h>
main(){int n,k=0;for(scanf("%d",&n);++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)printf("%d,",n);}
polfosol ఠ_ఠ
fuente
Dos cosas menores para el golf: =0después kse pueden eliminar, ya que es 0por defecto. std::cin>>n;while(++k<<k<n);puede ser for(std::cin>>n;++k<<k<n;);. También tengo la sensación de que for(n-=k;n>0;k*=2,n-=k+1)se puede simplificar de alguna manera combinando cosas, pero no estoy seguro de cómo. PD: Cambiar el delimitador de coma a un espacio se ve un poco mejor ya que no ves el último imo, pero esto es puramente cosmético :)
Kevin Cruijssen
1
@KevinCruijssen Gracias, pero algunos compiladores no asignan un valor predeterminado a las variables no estáticas. Entonces pensé que =0era necesario para la portabilidad;) También me di cuenta de que el espacio posterior #includeno es necesario.
polfosol ఠ_ఠ
Ah ok No conozco C ++ demasiado bien, así que he usado ese compilador en línea que vinculaste en tu respuesta para probar algunas cosas. :) Olvidaste el segundo cambio que propuse en mi comentario: el bucle while a un bucle for y poner el std::cin>>ninterior.
Kevin Cruijssen
103 bytes
ceilingcat
1

Retina 0.8.2 , 61 bytes

.+
11,$&$*
+`\b(1+),(\1(1*)1?\3)$
1$2¶1$1,$3
1+,
1
1A`
1+
$.&

Pruébalo en línea! 1 puerto indexado de la respuesta de @ Grimy. Explicación:

.+
11,$&$*

Comience con N=2y la entrada convertida a unario.

+`\b(1+),(\1(1*)1?\3)$

Repetidamente trate de restar Nde la entrada y luego divida por 2.

1$2¶1$1,$3

Si tiene éxito, recuerde 1 más que la entrada en la línea anterior, incremente Nen la línea actual y actualice la entrada al nuevo valor.

1+,
1

Elimine Ne incremente el último valor para que también esté indexado en 1.

1A`

Elimine la entrada original incrementada.

1+
$.&

Convierte los resultados a decimal.

Neil
fuente
1

Ruby , 62 bytes

->n{(1...c=(0..n).find{|r|n<r<<r}).map{|b|[n,b-c+(c<<b)].min}}

Pruébalo en línea!

Principalmente robado de la respuesta Python de TFeld.

GB
fuente