tło

Mam kilka kwadratowych pudeł równej wielkości, a ponieważ jestem zgrabną osobą, chcę ułożyć je wszystkie w kwadratową formację. Jednak ich liczba niekoniecznie jest kwadratem idealnym, więc może być konieczne przybliżenie kwadratu. Chcę, żebyś znalazł mi najbardziej estetyczny układ - oczywiście programowo.

Wejście

Twój wkład to pojedyncza dodatnia liczba całkowita kreprezentująca liczbę pól.

Wynik

Twój program wybierze dwie liczby całkowite dodatnie m, n, które będą się m*(n-1) < k ≤ m*nutrzymywać. Reprezentują szerokość i wysokość dużego, kwadratowego kształtu, który układamy. Ponieważ szukamy estetycznych kształtów, ilość powinna być minimalna, aby kształt był zbliżony do kwadratu, a jego powierzchnia była bliska . Jeśli nadal jest kilku kandydatów do pary , wybierz ten, w którym szerokość jest maksymalna.(m - n)2 + (m*n - k)2k(m, n)m

Teraz twoim faktycznym wyjściem nie będą liczby mi n. Zamiast tego wydrukujesz układ pudeł, używając znaku #do przedstawienia pudełka. Mówiąc dokładniej, wydrukujesz n-1wiersze, z których każdy składa się ze mznaków #, a następnie jeden wiersz k - m*(n-1)znaków #. Zauważ, że wynik zawiera dokładnie kznaki #.

Zasady i punktacja

Na wyjściu nie może być żadnych początkowych ani końcowych białych znaków, z wyjątkiem tego, że ostatni wiersz może być wypełniony końcowymi spacjami o długości m, jeśli jest to pożądane. Może być jedna nowa linia, ale nie ma poprzedniej nowej linii. W #razie potrzeby możesz użyć dowolnego drukowalnego znaku ASCII .

Możesz napisać pełny program lub zwrócić ciąg znaków z funkcji. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Oto prawidłowe dane wyjściowe dla kilku wartości wejściowych.

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

Pyth, 28 bajtów

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

Wypróbuj online.

Najważniejsze jest to, że sortuję potencjalne m według następującej właściwości:

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

Zwróć uwagę na całkowity brak n. Całkowity kształt jest określony jedynie przez m. Następnie przekształcam powyższą właściwość jeszcze raz, a moja ostateczna waga sortowania jest zdefiniowana jako odległość euklidesowa między następującymi dwoma punktami:

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

Zmienia to wartości masy, ale nie ich kolejność.

Python 3, 202 bajty

Wiem, że jest dłuższy niż rozwiązania CJam lub Pyth, ale mimo to oto sposób rozwiązania tego problemu w Pythonie:

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

Podstawową zasadą jest to, że wiemy, że m i n są mniejsze niż k. Również m * n> = k. Oznacza to, że możemy po prostu znaleźć minimum wyrażenia podanego w wyzwaniu dla wszystkich m, n <k, wyłączając wartości, których iloczyn jest większy niż k.

CJam ( 44 42 bajty)

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

Demo online

Raczej spodziewałem się, że będzie prostsze rozwiązanie z pierwiastkami kwadratowymi, ale wcale nie jest takie proste. Np. Dla danych wejściowych 31szerokość rzędu jest o dwa razy większa niż sufit pierwiastka kwadratowego; dla 273(pierwiastek kwadratowy nieco powyżej 16,5) najlepszym przybliżonym kwadratem jest idealny prostokąt 21x13.

CJam, 42 bajty

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

Wypróbuj online

Wyjaśnienie:

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.