¡Divide los pedazos!

17

Definimos como la lista de potencias distintas de que suman . Por ejemplo, .2 x V ( 35 ) = [ 32 , 2 , 1 ]V(X)2XV(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 MnorteV(N)2M

Mi,j=V(P)i×V(Q)j

donde y son los factores primos de .Q NPQN

Esto es mucho más fácil de entender con algunos ejemplos.

Ejemplo 1

Para , tenemos:N=21

  • V(N)=[16,4,1]
  • P=7 y V(P)=[4,2,1]
  • Q=3 y V(Q)=[2,1]
  • M=(842421)

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 1V(N)M168+4+442+21

[[8,4,4],[2,2],[1]]

Otra salida válida es:

[[8,4,2,2],[4],[1]]

Ejemplo # 2

Para , tenemos:N=851

  • V(N)=[512,256,64,16,2,1]
  • P=37 yV(P)=[32,4,1]
  • Q=23 yV(Q)=[16,4,2,1]
  • M=(512641612816464823241)

Una salida posible es:

[[512],[128,64,64],[32,16,16],[8,4,4],[2],[1]]

Reglas

  • Debido a que factorizar no es la parte principal del desafío, alternativamente puede tomar y como entrada.NPQ
  • 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 ).[[3,2,2],[1,1],[0]][[8,4,4],[2,2],[1]]
  • 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 = 15V(N)M[[8],[4],[2],[1]]N=15
  • Este es el !

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 ] ]
Arnauld
fuente
podemos tomar P y Q en lugar de N?
ngn
@ngn Voy a decir que sí, porque factorizar N no es la parte principal del desafío.
Arnauld
1
¿Podemos devolver la salida aplanada?
Erik the Outgolfer
@EriktheOutgolfer ... La salida aplanada es solo una partición de la entrada (1 + 2 + 2 + 4 = 9, por ejemplo). No creo que deba permitirse
Sr. Xcoder
@EriktheOutgolfer No creo que pueda ser inequívoco de esta manera, ya que el último término de una sublista puede ser el mismo que el primer término de la siguiente.
Arnauld

Respuestas:

4

K (ngn / k) , 66 63 bytes

{(&1,-1_~^(+\*|a)?+\b)_b:b@>b:,/*/:/2#a:{|*/'(&|2\x)#'2}'x,*/x}

Prué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

ngn
fuente
3

Jalea , 24 bytes

BṚT’2*
Ç€×þ/FṢŒṖ§⁼Ç}ɗƇPḢ

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.M1M4M=[[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.

BṚT’2* - Link 1, powers of 2 that sum to N: integer, N    e.g. 105
B      - binary                                                [1,1,0,1,0,0,1]
 Ṛ     - reverse                                               [1,0,0,1,0,1,1]
  T    - truthy indices                                        [1,4,6,7]
   ’   - decrement                                             [0,3,5,6]
    2  - literal two                                           2
     * - exponentiate                                          [1,8,32,64]

Ç€×þ/FṢŒṖ§⁼Ç}ɗƇPḢ - Main Link: list of two integers, [P,Q]
Ç€                - call last Link (1) as a monad for €ach
    /             - reduce with:
   þ              -   table with:
  ×               -     multiplication
     F            - flatten
      Ṣ           - sort
       ŒṖ         - all partitions
              Ƈ   - filter keep if:
             ɗ    -   last three links as a dyad:
         §        -     sum each
            }     -     use right...
               P  -       ...value: product (i.e. P×Q)
           Ç      -       ...do: call last Link (1) as a monad
          ⁼       -     equal? (non-vectorising so "all equal?")
                Ḣ - head
Jonathan Allan
fuente
3

Python 2 , 261 233 232 231 bytes

g=lambda n,r=[],i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
 V=[[v]for v in g(p*q)];i=j=0
 for m in sorted(-a*b for a in g(p)for b in g(q)):
	v=V[i]
	while-m<v[j]:v[j:j+1]=[v[j]/2]*2
	i,j=[i+1,i,0,j+1][j+1<len(v)::2]
 return V

Prué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.

Chas Brown
fuente
-k-1puede ser ~k.
Jonathan Frech
La i,jasignación puede ser i,j=[i+1,i,0,j+1][j+1<len(v)::2]por -1 byte
Jo King
@Jo King: Jajaja! Eso está retorcido!
Chas Brown
while v[j]>-mpuede serwhile-m<v[j]
Kevin Cruijssen
@ Kevin Cruijssen: Sí, de hecho. ¡Gracias!
Chas Brown
2

Jalea , 41 bytes

Œṗl2ĊƑ$Ƈ
PÇIP$ƇṪÇ€Œpµ³ÇIP$ƇṪƊ€ŒpZPṢ⁼FṢ$µƇ

Pruébalo en línea!

ÇIP$Ƈ[P,Q]

Sr. Xcoder
fuente
No es que sea un problema, pero no es exactamente rápido, ¿verdad? :)
Arnauld
@Arnauld Utiliza aproximadamente 3 funciones de partición de enteros en una sola ejecución :) Por supuesto que no es demasiado rápido
Sr. Xcoder
Ahora esperando ser superado. Creo que es posible en el sub-35/30, pero no creo que pueda hacer nada mucho más corto
Sr. Xcoder
2

Jalea , 34 bytes

BṚT’2*
PÇŒṗæḟ2⁼ƊƇ€ŒpẎṢ⁼Ṣ}ʋƇÇ€×þ/ẎƊ

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.

Erik el Outgolfer
fuente
1

Haskell, 281 195 bytes

import Data.List
r=reverse.sort
n#0=[]
n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=[]
m!x=m!!0:tail m!(x-m!!0)
m%[]=[]
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))
Евгений Новиков
fuente
1
Aquí hay algunos consejos: definir operadores en lugar de funciones binarias es más barato, reorganizar las protecciones y la coincidencia de patrones puede ahorrarle (==), usar en 1>0lugar de Truey no usar where. También n'se puede acortar. Con esto puede guardar 72 bytes: ¡ Pruébelo en línea!
ბიმო
Por cierto. debe consultar la sección de consejos de Haskell si no lo ha hecho.
ბიმო
Eché un vistazo a la situación de guardia nuevamente, otros 13 bytes menos: ¡ Pruébelo en línea!
ბიმო
@ OMᗺ, gracias. Soy nuevo en Haskell, por lo que este aspecto para mí como trucos de magia
Евгений Новиков
No se preocupe :) En caso de que tenga preguntas, no dude en preguntar en Of Monads and Men .
ბიმო