Dengan bilangan bulat positif di bawah 1000, tampilkan semua segi empat yang mungkin dengan area itu.

Tugas

Katakanlah inputnya adalah 20. Kita bisa membuat persegi panjang 20 × 1, 10 × 2, atau 5 × 4, jadi ini adalah output yang valid:

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

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

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

Perhatikan bahwa setiap kotak yang mungkin muncul persis sekali.

Persegi panjang mungkin muncul dalam urutan, orientasi, atau posisi apa pun, tetapi tidak ada dua persegi panjang yang bisa tumpang tindih atau menyentuh, bahkan di sudut-sudutnya. Berikut ini juga valid:

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

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

Mencetak gol

Area kotak pembatas (BBA) dari output adalah area persegi panjang minimum yang melingkupi semua persegi panjang. Pada contoh output pertama, ukurannya adalah 20 × 9, jadi BBA adalah 180. Pada output contoh kedua, ukurannya adalah 20 × 7, jadi BBA hanya 140.

Temukan BBA dari output ketika inputnya adalah 60, 111, 230, 400, dan 480, dan tambahkan. Lipat gandakan jumlah ini dengan ukuran kode Anda dalam byte. Hasilnya adalah skor Anda; kemenangan skor terendah.

Aturan

• Program (atau fungsi) harus menghasilkan output yang valid untuk setiap bilangan bulat positif di bawah 1000.
• Output harus mengandung hanya tanda bintang ( *), spasi ( ), dan baris baru.
• Mungkin ada jumlah ruang antara persegi panjang, tetapi ini diperhitungkan BBA.
• Leading atau trailing lines atau kolom, jika hanya memiliki spasi, tidak diperhitungkan BBA.

Ruby, 228 byte * 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}

Beberapa perubahan dari kode ungolfed. Yang terbesar adalah perubahan makna variabel mdari tinggi persegi panjang kuadrat, ke tinggi persegi panjang kuadrat plus n.

Sepele, *40telah diubah *nyang berarti banyak ruang putih yang tidak perlu di sebelah kanan untuk besar n; dan -2diubah menjadi 0yang berarti persegi panjang diplot di bagian bawah selalu kehilangan dua kolom pertama (ini menghasilkan pengepakan yang lebih buruk untuk angka yang hanya faktorisasi (n/2)*2)

Penjelasan

Saya akhirnya menemukan waktu untuk kembali ke ini.

Untuk diberikan n, bidang terkecil harus memiliki ruang yang cukup untuk persegi panjang terpanjang 1*ndan persegi panjang paling langka x*y. Seharusnya jelas bahwa tata letak terbaik dapat dicapai jika kedua persegi panjang memiliki sisi panjangnya yang berorientasi pada arah yang sama.

Mengabaikan persyaratan spasi putih di antara persegi panjang, kami menemukan bahwa total area adalah salah satu (n+y)*x = (n+n/x)*xatau n*(x+1). Either way, ini dievaluasi menjadi n*x + n. Termasuk spasi putih, kita harus memasukkan tambahan xjika kita menempatkan persegi panjang ujung ke ujung, atau njika kita menempatkan persegi panjang berdampingan. Karena itu yang pertama lebih disukai.

Ini memberikan lowerbound berikut (n+y+1)*xuntuk area lapangan:

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

Ini menyarankan algoritma berikut:

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

Sebenarnya mungkin untuk mendapatkan semua persegi panjang untuk kasus uji yang diperlukan dalam batas bawah yang disebutkan di atas, dengan pengecualian 60, yang menghasilkan 71 * 8 = 568 output berikut. Ini dapat ditingkatkan sedikit menjadi 60 * 9 = 540 dengan memindahkan dua persegi panjang tertipis ke kanan menjadi satu kotak lalu naik, tetapi penghematannya minimal, jadi mungkin tidak ada gunanya kode tambahan.

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

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

Ini memberi total area 21895.

Kode tidak dikunci

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 byte = 2801935

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

Uji di sini. Gunakan skrip ini untuk menghitung BBA.

Ini hanyalah solusi naif untuk memulai sesuatu.

Ruby, 56 byte

90385 * 56 = 5061560 dengan asumsi output sama dengan Martin (saya percaya begitu.)

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

Inilah fungsi lain yang bermanfaat, dalam program uji yang berguna

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]

Yang memberikan output berikut, untuk referensi:

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