Dado un entero positivo por debajo de 1000, muestre todos los rectángulos posibles con esa área.

Tarea

Digamos que la entrada es 20. Podemos hacer un rectángulo de 20 × 1, 10 × 2 o 5 × 4, por lo que esta es una salida válida:

********************

**********
**********

*****
*****
*****
*****

Tenga en cuenta que cada posible rectángulo aparece exactamente una vez.

Los rectángulos pueden aparecer en cualquier orden, orientación o posición, pero no pueden superponerse o tocarse dos rectángulos, incluso en las esquinas. Lo siguiente también es válido:

********************

            ****
**********  ****
**********  ****
            ****
            ****

Puntuación

El área del cuadro delimitador (BBA) de una salida es el área del rectángulo mínimo que encierra todos los rectángulos. En el primer ejemplo de salida, el tamaño es 20 × 9, por lo que el BBA es 180. En el segundo ejemplo de salida, el tamaño es 20 × 7, por lo que el BBA es solo 140.

Encuentre el BBA de la salida cuando la entrada sea 60, 111, 230, 400 y 480, y sume. Multiplique esta suma por el tamaño de su código en bytes. El resultado es tu puntaje; gana el puntaje más bajo.

Reglas

• El programa (o función) debe producir una salida válida para cualquier entero positivo por debajo de 1000.
• La salida debe contener solo asteriscos ( *), espacios ( ) y líneas nuevas.
• Puede haber cualquier cantidad de espacio entre los rectángulos, pero esto cuenta para el BBA.
• Las líneas o columnas iniciales o finales, si solo tienen espacios, no cuentan para el BBA.

Rubí, 228 bytes * 21895 = 4992060

->n{a=(0..n*2).map{$b=' '*n}
g=0
m=n*2
(n**0.5).to_i.downto(1){|i|n%i<1&&(m=[m,n+h=n/i].min
g+=h+1
g<m+2?(a[g-h-1,1]=(1..h).map{?**i+$b}):(x=(m-h..m).map{|j|r=a[j].rindex(?*);r ?r:0}.max 
(m-h+1..m).each{|j|a[j][x+2]=?**i}))}
a}

Varios cambios de código no golfizado. El más grande es el cambio de significado de la variable mdesde la altura del rectángulo más cuadrado, hasta la altura del rectángulo más cuadrado más n.

Trivialmente, *40se ha cambiado a lo *nque significa una gran cantidad de espacios en blanco innecesarios a la derecha para grandes n; y -2se cambia a lo 0que significa que los rectángulos trazados en la parte inferior siempre pierden las dos primeras columnas (esto da como resultado un embalaje más pobre para los números cuya única factorización es (n/2)*2)

Explicación

Finalmente encontré tiempo para volver a esto.

Para un determinado, nel campo más pequeño debe tener suficiente espacio para el rectángulo más largo 1*ny el rectángulo más cuadrado x*y. Debería ser evidente que el mejor diseño se puede lograr si ambos rectángulos tienen sus lados largos orientados en la misma dirección.

Ignorando el requisito de espacio en blanco entre los rectángulos, encontramos que el área total es (n+y)*x = (n+n/x)*xo n*(x+1). De cualquier manera, esto se evalúa como n*x + n. Incluyendo el espacio en blanco, tenemos que incluir un extra xsi colocamos los rectángulos de extremo a extremo, o nsi colocamos los rectángulos uno al lado del otro. Por lo tanto, lo primero es preferible.

Esto proporciona los siguientes límites inferiores (n+y+1)*xpara el área de campo:

n     area
60    71*6=426
111  149*3=447
230  254*10=2540
400  421*20=8240
480  505*20=10100

Esto sugiere el siguiente algoritmo:

Find the value (n+y+1) which shall be the field height
Iterate from the squarest rectangle to the longest one
  While there is space in the field height, draw each rectangle, one below the other, lined up on the left border.
  When there is no more space in the field height, draw the remaining rectangles, one beside the other, along the bottom border, taking care not to overlap any of the rectangles above.
  (Expand the field rightwards in the rare cases where this is necessary.)

En realidad, es posible obtener todos los rectángulos para los casos de prueba requeridos dentro de los límites inferiores mencionados anteriormente, con la excepción de 60, que proporciona el siguiente resultado de 71 * 8 = 568. Esto se puede mejorar ligeramente a 60 * 9 = 540 moviendo los dos rectángulos más delgados a la derecha un cuadrado y luego hacia arriba, pero el ahorro es mínimo, por lo que probablemente no valga ningún código adicional.

10
12
15
20
30
60
******
******
******
******
******
******
******
******
******
******

*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
*****  *
       *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
****   *
       *
***    *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
*** ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *
    ** *

Esto da un área total de 21895.

Código sin golf

f=->n{
  a=(0..n*2).map{' '*40}                                      #Fill an array with strings of 40 spaces
  g=0                                                         #Total height of all rectangles
  m=n                                                         #Height of squarest rectangle (first guess is n) 
  (n**0.5).to_i.downto(1){|i|n%i<1&&(puts n/i                 #iterate through widths. Valid ones have n%i=0. Puts outputs heights for debugging.
    m=[m,h=n/i].min                                           #Calculate height of rectangle. On first calculation, m will be set to height of squarest rectangle.
    g+=h+1                                                    #Increment g
    g<n+m+2?                                                  #if the rectangle will fit beneath the last one, against the left margin
      (a[g-h-1,1]=(1..h).map{'*'*i+' '*40})                      #fill the region of the array with stars
    :                                                         #else  
      (x=(n+m-h..n+m).map{|j|r=a[j].rindex('* ');r ?r:-2}.max    #find the first clear column
      (n+m-h+1..n+m).each{|j|a[j][x+2]='*'*i}                    #and plot the rectangle along the bottom margin
    )
  )}
a}                                                            #return the array

puts f[gets.to_i]

CJam, 90385 * 31 bytes = 2801935

q~:FmQ,:){F\%!},{F\/F'**/N*NN}/

Pruébalo aquí. Use este script para calcular los BBA.

Esta es solo la solución ingenua para comenzar las cosas.

Ruby, 56 bytes

90385 * 56 = 5061560 suponiendo que la salida sea igual a la de Martin (creo que es).

->n{1.upto(n){|i|i*i<=n&&n%i==0&&puts([?**(n/i)]*i,'')}}

Aquí hay otra función útil, en un programa de prueba útil

f=->n{1.upto(n){|i|i*i<=n&&n%i==0&&print(n/i,"*",i,"\n")};puts}

f[60];f[111];f[230];f[400];f[480]

Lo que da el siguiente resultado, para referencia:

60*1
30*2
20*3
15*4
12*5
10*6

111*1
37*3

230*1
115*2
46*5
23*10

400*1
200*2
100*4
80*5
50*8
40*10
25*16
20*20

480*1
240*2
160*3
120*4
96*5
80*6
60*8
48*10
40*12
32*15
30*16
24*20