Étant donné un entier positif inférieur à 1000, affichez tous les rectangles possibles avec cette zone.

Tâche

Disons que l'entrée est 20. Nous pouvons faire un rectangle de 20 × 1, 10 × 2 ou 5 × 4, c'est donc une sortie valide:

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

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

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

Notez que chaque rectangle possible apparaît exactement une fois.

Les rectangles peuvent apparaître dans n'importe quel ordre, orientation ou position, mais pas deux rectangles peuvent se chevaucher ou se toucher, même aux coins. Ce qui suit est également valable:

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

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

Notation

La zone de zone englobante (BBA) d'une sortie est la zone du rectangle minimal entourant tous les rectangles. Dans le premier exemple de sortie, la taille est de 20 × 9, donc le BBA est de 180. Dans le deuxième exemple de sortie, la taille est de 20 × 7, donc le BBA n'est que de 140.

Trouvez le BBA de la sortie lorsque l'entrée est 60, 111, 230, 400 et 480, et additionnez-les. Multipliez cette somme par la taille de votre code en octets. Le résultat est votre score; le score le plus bas l'emporte.

Règles

• Le programme (ou la fonction) doit produire une sortie valide pour tout entier positif inférieur à 1000.
• La sortie doit contenir uniquement des astérisques ( *), des espaces ( ) et des retours à la ligne.
• Il peut y avoir n'importe quelle quantité d'espace entre les rectangles, mais cela compte pour le BBA.
• Les lignes ou colonnes de début ou de fin, si elles n'ont que des espaces, ne comptent pas pour le BBA.

Rubis, 228 octets * 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}

Plusieurs changements par rapport au code non golfé. Le plus grand est le changement de signification de la variable mde la hauteur du rectangle le plus carré à la hauteur du rectangle le plus carré plus n.

Trivial, *40a été changé en *nce qui signifie beaucoup d'espace blanc inutile à droite pour les grands n; et -2est changé en 0ce qui signifie que les rectangles tracés en bas manquent toujours les deux premières colonnes (cela se traduit par un emballage moins bon pour les nombres dont la seule factorisation est (n/2)*2)

Explication

J'ai enfin trouvé le temps d'y revenir.

Pour une donnée, nle plus petit champ doit avoir suffisamment d'espace pour le rectangle le plus long 1*net le rectangle le plus carré x*y. Il doit être évident que la meilleure disposition peut être obtenue si les deux rectangles ont leurs côtés longs orientés dans la même direction.

En ignorant l'exigence d'espace blanc entre les rectangles, nous constatons que la surface totale est soit (n+y)*x = (n+n/x)*xou n*(x+1). Dans les deux cas, cela est évalué n*x + n. Y compris les espaces, nous devons inclure un supplément xsi nous plaçons les rectangles bout à bout, ou nsi nous plaçons les rectangles côte à côte. Le premier est donc préférable.

Cela donne les limites inférieures suivantes (n+y+1)*xpour la zone de champ:

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

Cela suggère l'algorithme suivant:

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.)

Il est en fait possible d'obtenir tous les rectangles pour les cas de test requis dans les limites inférieures mentionnées ci-dessus, à l'exception de 60, ce qui donne la sortie 71 * 8 = 568 suivante. Cela peut être légèrement amélioré à 60 * 9 = 540 en déplaçant les deux rectangles les plus minces vers la droite, puis vers le haut, mais l'économie est minime, donc cela ne vaut probablement pas de code supplémentaire.

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

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

Cela donne une superficie totale de 21895.

Code non 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 octets = 2801935

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

Testez-le ici. Utilisez ce script pour calculer les BBA.

Ceci est juste la solution naïve pour faire démarrer les choses.

Rubis, 56 octets

90385 * 56 = 5061560 en supposant une sortie identique à celle de Martin (je crois que oui.)

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

Voici une autre fonction utile, dans un programme de test utile

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]

Ce qui donne la sortie suivante, pour référence:

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