Perkiraan Formasi Kuadrat

11

Latar Belakang

Saya memiliki banyak kotak berbentuk persegi dengan ukuran yang sama, dan karena saya orang yang rapi, saya ingin mengatur semuanya menjadi formasi persegi. Namun, jumlah mereka belum tentu kuadrat sempurna, jadi saya mungkin harus mendekati bentuk persegi. Saya ingin Anda menemukan pengaturan yang paling menyenangkan bagi saya - secara terprogram, tentu saja.

Memasukkan

Input Anda adalah bilangan bulat positif tunggal k, mewakili jumlah kotak.

Keluaran

Program Anda harus memilih dua bilangan bulat positif m, nyang m*(n-1) < k ≤ m*nberlaku. Mereka mewakili lebar dan tinggi dari bentuk persegi besar seperti yang kita atur. Karena kita mencari bentuk yang secara estetika menyenangkan, jumlahnya harus minimal, sehingga bentuknya dekat dengan kotak, dan luasnya dekat . Jika masih ada beberapa kandidat untuk pasangan , pilih salah satu yang lebarnya maksimal.(m - n)2 + (m*n - k)2k(m, n)m

Sekarang, hasil aktual Anda tidak akan menjadi angka mdan n. Sebagai gantinya, Anda harus mencetak susunan kotak, menggunakan karakter #untuk mewakili kotak. Lebih khusus lagi, Anda harus mencetak n-1baris, yang masing-masing terdiri dari mkarakter #, dan kemudian satu baris k - m*(n-1)karakter #. Perhatikan bahwa output mengandung kkarakter yang tepat #.

Aturan dan Penilaian

Tidak akan ada spasi putih terdepan atau tertinggal dalam output, kecuali bahwa baris terakhir dapat diisi dengan spasi tambahan m, jika diinginkan. Mungkin ada satu trailing newline, tetapi tidak ada newlines sebelumnya. Anda dapat menggunakan karakter ASCII yang dapat dicetak sebagai pengganti #, jika diinginkan.

Anda dapat menulis program lengkap, atau mengembalikan string dari suatu fungsi. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji Kasus

Berikut adalah output yang benar untuk beberapa nilai input.

1
#
2
##
3
##
#
4
##
##
8
###
###
##
13
#####
#####
###
17
######
######
#####
18
#####
#####
#####
###
20
#####
#####
#####
#####
21
######
######
######
###
22
######
######
######
####
23
#####
#####
#####
#####
###
Zgarb
sumber

Jawaban:

6

Pyth, 28 byte

jbc*\#Qho.a,,N*NJ_/_QN,JQ_SQ

Cobalah online.

Intinya adalah bahwa saya mengurutkan potensial pada properti berikut:

(m - ceil(k/m))^2 + (m*ceil(k/m) - k)^2

Perhatikan ketidakhadiran total n. Bentuk total didefinisikan hanya oleh m. Kemudian saya mengubah properti di atas sekali lagi, dan berat penyortiran terakhir saya didefinisikan sebagai jarak Euclidean antara dua titik berikut:

(m, m*ceil(k/m)) and (ceil(k/m), k)

Ini mengubah nilai bobot, tetapi bukan urutannya.

orlp
sumber
3

Python 3, 202 byte

Saya tahu bahwa ini lebih lama daripada solusi CJam atau Pyth, namun demikian, berikut adalah cara untuk memecahkan masalah ini dengan Python:

k=int(input())
r,d,s=range(k+1),{},'#'*k
for n in r:
 for m in r:
  if m*n>=k:
   d[m,n]=(m-n)**2+(m*n-k)**2
x,y=max(i for i in d.keys()if d[i]==min(d.values()))
[print(s[i*x:(i*x+x])for i in range(y+1)]

Prinsip dasarnya adalah bahwa kita tahu m dan n keduanya kurang dari k. Juga, m * n> = k. Itu berarti bahwa kita dapat dengan mudah menemukan ekspresi minimum yang diberikan dalam tantangan untuk semua m, n <k, tidak termasuk nilai yang produknya lebih besar dari k.

Anthony Roitman
sumber
Saya sebenarnya menghitung 231 byte di sumber Anda, bukan 234. Namun, Anda dapat menguranginya dengan mengurangi ukuran indentasi Anda dari empat spasi menjadi satu ruang. Itu akan bekerja sama.
Alex A.
Ini adalah alat yang berguna untuk mendapatkan jumlah byte Anda. Omong-omong, pengiriman bagus dan selamat datang di situs!
Alex A.
:hilang pada baris 5. Koma adalah yang mendefinisikan tupel, tanda kurung ()dapat dihapus pada baris 6. Spasi antara )dan ( ifatau for) juga. maxbisa mendapatkan generator sebagai parameter, sehingga tanda kurung []redundan. Anda beralih pada dkunci, sehingga Anda dapat menggunakan dengan aman d[i].
Trang Oul
Anda dapat menyimpan dua byte yang berubah (i+1)*xmenjadi -~i*xatau i*x+x.
Kade
Anda memiliki paren tambahan yang tidak valid di (i*x+x...
FlipTack
2

CJam ( 44 42 bytes)

qi_,{)_2$d\/m]_2$-_*@@*2$-_*+~}$W=)'#@*/N*

Demo online

Saya agak berharap ada solusi sederhana yang melibatkan akar kuadrat, tetapi sama sekali tidak sesederhana itu. Misalnya untuk input 31, lebar baris dua lebih besar dari plafon akar kuadrat; untuk 273(akar kuadrat lebih dari 16,5) kuadrat perkiraan terbaik adalah persegi panjang 21x13 sempurna.

Peter Taylor
sumber
1

CJam, 42 byte

li:K_,f-{:XdK\/m]:YX-_*XY*K-_*+}$0='#K*/N*

Cobalah online

Penjelasan:

li    Get and interpret input.
:K    Store in variable K for later use.
_     Copy.
,     Build sequence [0 .. K-1].
f-    Subtract from K, to get sequence [K .. 1]. Larger values have to come
      first so that they are ahead in ties when we sort later.
{     Begin block for calculation of target function for sort.
  :X    Store width in variable X.
  d     Convert to double.
  K\/   Calculate K/X.
  m]    Ceiling.
  :Y    Store height in variable Y.
  X-    Calculate Y-X.
  _*    Square it.
  XY*   Calculate X*Y...
  K-    ... and X*Y-K
  _*    Square it.
  +     Add the two squares.
}$    Sort by target function value.
0=    Get first element, this is the best width.
'#K*  Build string of K '# characters.
/     Split using width.
N*    Join with newlines.
Reto Koradi
sumber