Definimos como la lista de potencias distintas de que suman . Por ejemplo, .2 x V ( 35 ) = [ 32 , 2 , 1 ]
Por convención, los poderes se ordenan aquí de mayor a menor. Pero no afecta la lógica del desafío, ni las soluciones esperadas.
Tarea
Dado un semiprime , reemplace cada término en con otra lista de potencias de que suma a este término, de tal manera que la unión de todas las sublistas resultantes sea una cobertura exacta de la matriz definida como:V ( N ) 2 M
donde y son los factores primos de .Q N
Esto es mucho más fácil de entender con algunos ejemplos.
Ejemplo 1
Para , tenemos:
- y
- y
Para convertir en una cubierta exacta de , podemos dividir en y en , mientras que se modifica. Entonces, una salida posible es:M 16 8 + 4 + 4 4 2 + 2 1
Otra salida válida es:
Ejemplo # 2
Para , tenemos:
- y
- y
Una salida posible es:
Reglas
- Debido a que factorizar no es la parte principal del desafío, alternativamente puede tomar y como entrada.
- Cuando existen varias soluciones posibles, puede devolver solo una de ellas o todas.
- Alternativamente, puede devolver los exponentes de las potencias (por ejemplo, lugar de ).
- El orden de las sublistas no importa, ni el orden de los términos en cada sublista.
- Para algunas semiprimes, no tendrá que dividir ningún término porque ya es una cobertura perfecta de (consulte A235040 ). Pero aún debe devolver una lista de listas (singleton) como para .M [ [ 8 ] , [ 4 ] , [ 2 ] , [ 1 ] ] N = 15
- Este es el código de golf !
Casos de prueba
Input | Possible output
-------+-----------------------------------------------------------------------------
9 | [ [ 4, 2, 2 ], [ 1 ] ]
15 | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
21 | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
51 | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
129 | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
159 | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
161 | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
201 | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
403 | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
851 | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
2307 | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]
Respuestas:
K (ngn / k) ,
6663 bytesPruébalo en línea!
acepta (P; Q) en lugar de N
algoritmo:
calcular A como las sumas parciales de V (P * Q)
multiplique cada V (P) con cada V (Q), ordene los productos en orden descendente (llamémosle R) y calcule sus sumas parciales B
encuentre las posiciones de esos elementos en B que también ocurren en A; cortar R justo después de esas posiciones
fuente
Jalea , 24 bytes
Un enlace monádico que acepta una lista de dos enteros
[P, Q]
que produce una posible lista de listas como se describe en la pregunta.Pruébalo en línea! (el pie de página imprime una representación de cadena para mostrar la lista como realmente es)
O vea el conjunto de pruebas (tomando una lista de N y reordenando los resultados para que sean como los de la pregunta)
¿Cómo?
Siempre podemos dividir los elementos de de abajo hacia arriba, con avidez (hay un 1 en M o tuvimos una entrada de 4 , cuando M = [ [ 4 ] ] ) para encontrar una solución.M 1 M 4 M=[[4]]
Nota: el código recopila todas (¡una!) Soluciones de este tipo en una lista y luego toma el resultado del encabezado (solo), es decir, el encabezado final es necesario ya que las particiones no son de todos los ordenamientos posibles.
fuente
Python 2 ,
261233232231 bytesPruébalo en línea!
1 byte de Jo King ; y otro 1 byte debido a Kevin Cruijssen .
Toma como entrada
p,q
. Persigue el algoritmo codicioso.fuente
-k-1
puede ser~k
.i,j
asignación puede seri,j=[i+1,i,0,j+1][j+1<len(v)::2]
por -1 bytewhile v[j]>-m
puede serwhile-m<v[j]
Jalea , 41 bytes
Pruébalo en línea!
ÇIP$Ƈ
fuente
Jalea , 34 bytes
Pruébalo en línea!
Formato de entrada:
[P, Q]
(el enlace TIO anterior no acepta esto, sino un solo número, para ayudar con los casos de prueba).Formato de salida: Lista de todas las soluciones (se muestra como representación de cuadrícula de la lista 3D sobre TIO).
Velocidad: tortuga.
fuente
Pyth , 27 bytes
Pruébalo aquí!
fuente
Haskell,
281195 bytesfuente
(==)
, usar en1>0
lugar deTrue
y no usarwhere
. Tambiénn'
se puede acortar. Con esto puede guardar 72 bytes: ¡ Pruébelo en línea!