Biorąc pod uwagę dodatnią liczbę całkowitą poniżej 1000, wyświetl wszystkie możliwe prostokąty z tym obszarem.

Zadanie

Powiedzmy, że dane wejściowe to 20. Możemy zrobić prostokąt 20 × 1, 10 × 2 lub 5 × 4, więc jest to prawidłowy wynik:

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

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

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

Zauważ, że każdy możliwy prostokąt pojawia się dokładnie raz.

Prostokąty mogą pojawiać się w dowolnej kolejności, orientacji lub pozycji, ale żadne dwa prostokąty nie mogą się nakładać ani dotykać, nawet w rogach. Obowiązują również następujące zasady:

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

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

Punktacja

Obszar ramki granicznej (BBA) wyniku jest obszarem minimalnego prostokąta obejmującego wszystkie prostokąty. W pierwszym przykładzie wyjściowym rozmiar wynosi 20 × 9, więc BBA wynosi 180. W drugim przykładzie wyjściowym rozmiar wynosi 20 × 7, więc BBA ma tylko 140.

Znajdź BBA wyjścia, gdy wejście to 60, 111, 230, 400 i 480, i dodaj je. Pomnóż tę sumę przez rozmiar kodu w bajtach. Rezultatem jest twój wynik; najniższy wynik wygrywa.

Zasady

• Program (lub funkcja) musi generować prawidłowe dane wyjściowe dla dowolnej liczby całkowitej dodatniej poniżej 1000.
• Dane wyjściowe muszą zawierać tylko gwiazdki ( *), spacje ( ) i znaki nowej linii.
• Pomiędzy prostokątami może być dowolna ilość miejsca, ale ma to znaczenie dla BBA.
• Linie wiodące lub końcowe lub kolumny, jeśli mają tylko spacje, nie liczą się do BBA.

Rubinowy, 228 bajtów * 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}

Kilka zmian w stosunku do niepoznanego kodu. Największa jest zmiana znaczenia zmiennej mz wysokości prostokąta kwadratowego na wysokość prostokąta kwadratowego plus n.

Trywialnie *40został zmieniony na, *nco oznacza wiele niepotrzebnych białych znaków po prawej stronie dla dużych n; i -2zmienia się na, 0co oznacza, że ​​prostokąty narysowane wzdłuż dna zawsze pomijają dwie pierwsze kolumny (powoduje to gorsze upakowanie liczb, których jedynym rozkładem jest faktoryzacja (n/2)*2)

Wyjaśnienie

W końcu znalazłem czas, aby wrócić do tego.

Dla danego npola najmniejsze pole musi mieć wystarczająco dużo miejsca zarówno dla najdłuższego prostokąta, jak 1*ni kwadratu prostokąta x*y. Powinno być oczywiste, że najlepszy układ można osiągnąć, jeśli oba prostokąty mają długie boki ustawione w tym samym kierunku.

Nie zwracając uwagi na wymóg spacji między prostokątami, okazuje się, że całkowita powierzchnia jest albo (n+y)*x = (n+n/x)*xalbo n*(x+1). Tak czy inaczej, to ocenia n*x + n. Uwzględniając spację, musimy dodać dodatkowy, xjeśli umieszczamy prostokąty od końca do końca lub njeśli umieszczamy prostokąty obok siebie. Ten pierwszy jest zatem preferowany.

Daje to następujące dolne granice (n+y+1)*xobszaru pola:

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

Sugeruje to następujący algorytm:

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

Możliwe jest uzyskanie wszystkich prostokątów dla wymaganych przypadków testowych w wyżej wymienionych dolnych granicach, z wyjątkiem 60, co daje następującą wartość wyjściową 71 * 8 = 568. Można to nieco poprawić do 60 * 9 = 540, przesuwając dwa najcieńsze prostokąty o jeden kwadrat w prawo, a następnie w górę, ale oszczędność jest minimalna, więc prawdopodobnie nie jest wart żadnego dodatkowego kodu.

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

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

To daje łączną powierzchnię 21895.

Nieskluczony kod

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 bajtów = 2801935

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

Sprawdź to tutaj. Użyj tego skryptu, aby obliczyć BBA.

To tylko naiwne rozwiązanie, aby zacząć wszystko.

Rubinowy, 56 bajtów

90385 * 56 = 5061560 przy założeniu, że dane wyjściowe są takie same jak w przypadku Martina (tak mi się wydaje).

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

Oto kolejna przydatna funkcja w przydatnym programie testowym

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]

Co daje następujące dane wyjściowe:

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