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 = 15
ambos[3, 8]
y[4, 8]
son salidas válidas. - Puede devolver la lista o imprimirla con cualquier separador razonable.
- Este es el código de golf , 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.
fuente
1+2
. ¿De dónde vino la segunda cadena de 2 eslabones?Respuestas:
05AB1E ,
23118 bytesPruébalo en línea!
Utiliza indexación basada en 0.
Explicación:
иg
parece 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 ).fuente
Ø.Ø
. ¿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.Ø.Ø
realidad fue mi primera idea. Su comentario me inspiró para probar cosas al azar: me encontr鮟à
,ï®M
y lo más importante,иg
que 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.Python 2 , 75 bytes
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, 31
que da cadenas de4 1 8 1 16 1 32
(ordenados:1 1 1 4 8 16 32
.Todos los números se pueden hacer:
Otros ejemplos:
fuente
f=
al comienzo? Dado que usa una llamada af
en la función lambda, y solo puedo suponer que se refiere al mismo lambda que está definiendo.f
no es recursiva, pero se hace referencia en el código y, por lo tanto, debe nombrarse.R ,
7769 bytes-8 bytes gracias a Aaron Hayman
Pruébalo en línea!
(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):
Sia ( k ) es el entero más pequeño norte requiriendo k cortes, entonces a ( k ) es OEIS A134401 .
fuente
n=1
, pero una forma alternativa de generar los puntos de corte es la recurrencia1, 4, 4a(n-1)-4a(n-2)
.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.sum
lugar dematch
.Jalea , 12 bytes
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!
fuente
JavaScript (ES6), 66 bytes
Este es un puerto de la respuesta de TFeld .
Pruébalo en línea!
fuente
C ++,
109, 107 bytes-2 bytes gracias a Kevin
El algoritmo es similar a la respuesta de Robin Ryder. El código está escrito en una forma completa compilable. ¡Intentalo!
Detalles:
Esto tiene una variación de C con la misma longitud de bytes (no parece necesitar una respuesta por separado):
fuente
=0
despuésk
se pueden eliminar, ya que es0
por defecto.std::cin>>n;while(++k<<k<n);
puede serfor(std::cin>>n;++k<<k<n;);
. También tengo la sensación de quefor(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 :)=0
era necesario para la portabilidad;) También me di cuenta de que el espacio posterior#include
no es necesario.std::cin>>n
interior.Retina 0.8.2 , 61 bytes
Pruébalo en línea! 1 puerto indexado de la respuesta de @ Grimy. Explicación:
Comience con
N=2
y la entrada convertida a unario.Repetidamente trate de restar
N
de la entrada y luego divida por 2.Si tiene éxito, recuerde 1 más que la entrada en la línea anterior, incremente
N
en la línea actual y actualice la entrada al nuevo valor.Elimine
N
e incremente el último valor para que también esté indexado en 1.Elimine la entrada original incrementada.
Convierte los resultados a decimal.
fuente
Ruby , 62 bytes
Pruébalo en línea!
Principalmente robado de la respuesta Python de TFeld.
fuente