Dado um número inteiro positivo abaixo de 1000, exiba todos os retângulos possíveis com essa área.

Tarefa

Digamos que a entrada seja 20. Podemos fazer um retângulo 20 × 1, 10 × 2 ou 5 × 4, portanto, essa é uma saída válida:

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

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

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

Observe que cada retângulo possível aparece exatamente uma vez.

Os retângulos podem aparecer em qualquer ordem, orientação ou posição, mas dois retângulos podem se sobrepor ou tocar, mesmo nos cantos. O seguinte também é válido:

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

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

Pontuação

A área da caixa delimitadora (BBA) de uma saída é a área do retângulo mínimo que envolve todos os retângulos. No primeiro exemplo de saída, o tamanho é 20 × 9, então o BBA é 180. No segundo exemplo de saída, o tamanho é 20 × 7, então o BBA é apenas 140.

Encontre o BBA da saída quando a entrada for 60, 111, 230, 400 e 480 e adicione-os. Multiplique essa soma pelo tamanho do seu código em bytes. O resultado é sua pontuação; menor pontuação ganha.

Regras

• O programa (ou função) deve produzir uma saída válida para qualquer número inteiro positivo abaixo de 1000.
• A saída deve conter apenas asteriscos ( *), espaços ( ) e novas linhas.
• Pode haver qualquer quantidade de espaço entre os retângulos, mas isso conta para o BBA.
• Linhas ou colunas iniciais ou finais, se tiverem apenas espaços, não contam para o BBA.

Ruby, 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}

Várias mudanças no código não-destruído. A maior delas é a mudança de significado da variável mda altura do retângulo quadrado, para a altura do retângulo quadrado mais n.

Trivialmente, *40foi alterado para o *nque significa muito espaço em branco desnecessário à direita para grandes n; e -2é alterado para o 0que significa que os retângulos plotados na parte inferior sempre perdem as duas primeiras colunas (isso resulta em menor empacotamento para números cuja única fatoração é (n/2)*2)

Explicação

Finalmente encontrei tempo para voltar a isso.

Para um dado ncampo, o menor campo deve ter espaço suficiente para o retângulo mais longo 1*ne o mais quadrado x*y. Deve ficar claro que o melhor layout pode ser alcançado se ambos os retângulos tiverem os lados longos orientados na mesma direção.

Ignorando o requisito de espaço em branco entre os retângulos, descobrimos que a área total é (n+y)*x = (n+n/x)*xou n*(x+1). De qualquer maneira, isso avalia como n*x + n. Incluindo o espaço em branco, precisamos incluir um extra xse colocarmos os retângulos de ponta a ponta ou nse colocarmos os retângulos lado a lado. O primeiro é, portanto, preferível.

Isso fornece os seguintes limites inferiores (n+y+1)*xpara a á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

Isso sugere o seguinte 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.)

Na verdade, é possível obter todos os retângulos para os casos de teste necessários dentro dos limites inferiores mencionados acima, com exceção de 60, que fornece a seguinte saída de 71 * 8 = 568. Isso pode ser ligeiramente melhorado para 60 * 9 = 540 movendo os dois retângulos mais finos para a direita um quadrado e depois para cima, mas a economia é mínima, portanto provavelmente não vale nenhum código extra.

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

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

Isso fornece uma área total de 21895.

Código ungolfed

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}/

Teste aqui. Use este script para calcular os BBAs.

Esta é apenas a solução ingênua para começar.

Ruby, 56 bytes

90385 * 56 = 5061560 assumindo a mesma saída que a de Martin (acredito que seja).

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

Aqui está outra função útil, em um programa de teste ú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]

O que fornece a seguinte saída, para referência:

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