fundo

Tenho um monte de caixas quadradas de tamanho igual e, como sou uma pessoa elegante, quero organizá-las em uma formação quadrada. No entanto, o número deles não é necessariamente um quadrado perfeito; portanto, talvez seja necessário aproximar o formato do quadrado. Quero que você me encontre o arranjo mais esteticamente agradável - programaticamente, é claro.

Entrada

Sua entrada é um número inteiro positivo único k, representando o número de caixas.

Resultado

Seu programa deve escolher dois números inteiros positivos, m, ntal como m*(n-1) < k ≤ m*né o caso. Eles representam a largura e a altura da grande forma quadrada que estamos organizando. Como procuramos formas esteticamente agradáveis, a quantidade deve ser mínima, para que a forma fique próxima a um quadrado e sua área fique próxima . Se ainda houver vários candidatos para o par , escolha aquele em que a largura seja máxima.(m - n)2 + (m*n - k)2k(m, n)m

Agora, sua saída real não deve ser os números me n. Em vez disso, você deve imprimir o arranjo das caixas, usando o caractere #para representar uma caixa. Mais especificamente, você deve imprimir n-1linhas, cada uma das quais composta por mcaracteres #e, em seguida, uma linha de k - m*(n-1)caracteres #. Observe que a saída contém exatamente kcaracteres #.

Regras e Pontuação

Não deve haver nenhum espaço em branco à esquerda ou à direita na saída, exceto que a última linha pode ser preenchida com espaços à direita de comprimento m, se desejado. Pode haver uma nova linha final, mas nenhuma nova linha anterior. Você pode usar qualquer caractere ASCII imprimível no lugar de #, se desejado.

Você pode escrever um programa completo ou retornar uma string de uma função. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas.

Casos de teste

Aqui estão as saídas corretas para alguns valores de entrada.

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

Pitão, 28 bytes

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

Experimente online.

O ponto crucial é que eu classifico o potencial m na seguinte propriedade:

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

Observe a ausência total de n. A forma total é definida apenas por m. Depois, transformo a propriedade acima mais uma vez, e meu peso final de classificação é definido como a distância euclidiana entre os dois pontos a seguir:

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

Isso altera os valores de peso, mas não a ordem deles.

Python 3, 202 bytes

Eu sei que é mais longo que as soluções CJam ou Pyth, mas, no entanto, aqui está uma maneira de resolver esse problema no 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)]

O princípio básico é que sabemos que m e n são ambos menores que k. Além disso, m * n> = k. Isso significa que podemos simplesmente encontrar o mínimo da expressão dada no desafio para todos m, n <k, excluindo valores cujo produto é maior que k.

CJam ( 44 42 bytes)

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

Demonstração online

Eu esperava que houvesse uma solução mais simples envolvendo raízes quadradas, mas não é tão simples assim. Por exemplo, para entrada, 31a largura da linha é dois maior que o teto da raiz quadrada; para 273(raiz quadrada pouco mais de 16,5), o melhor quadrado aproximado é um retângulo 21x13 perfeito.

CJam, 42 bytes

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

Experimente online

Explicação:

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.