Você ensina uma classe de alunos com preferências interessantes sobre como as cadeiras são organizadas. Existem três requisitos muito específicos para a organização das cadeiras:

1. A maioria deles é organizada em um retângulo, mesmo que isso signifique que algumas cadeiras ficam vazias.

2. Deve haver o mínimo de cadeiras vazias possível.

3. Eles devem ser o mais "quadrado" possível. A quadratura é determinada pela distância entre a largura e a altura do retângulo, quanto menor, melhor. Por exemplo, um retângulo 4x7com um quadrado de 3.

Para ser mais específico, a "pontuação" de um arranjo é a distância entre a largura e a altura, mais o número de cadeiras que ficariam vazias.

Vamos dar um exemplo. Digamos que você tenha 13 alunos. Você pode organizar as cadeiras de qualquer uma das seguintes maneiras:

1x13
2x7
3x5
4x4

1x13não é muito quadrado. De fato, 1 e 13 são 12 separados, então damos a esse arranjo 12 pontos. Ele também tem 0 cadeiras vazias, então adicionamos 0 pontos, dando a esse arranjo uma pontuação de 12. Não é tão bom assim.

2x7é certamente melhor. 2 e 7 são separados apenas por 5, por isso damos 5 pontos a esse arranjo. No entanto, se você realmente organizasse duas fileiras de sete cadeiras, seriam 14 cadeiras, o que significa que uma cadeira estaria vazia. Então, adicionamos um ponto, atribuindo a esse arranjo uma pontuação de 6.

Nós também poderíamos fazer 3x5. 3 e 5 são 2 separados, então +2 pontos. São necessárias 15 cadeiras, o que significa que teríamos duas cadeiras extras, mais outros 2 pontos, para uma pontuação de 4.

Última opção 4x4. 4 e 4 são 0 separados, portanto, atribuímos +0 pontos. O 4x4 ocupa 16 cadeiras, portanto, 3 cadeiras ficam vazias, obtendo uma pontuação total de 3. Essa é a solução ideal.

Em caso de empate, a solução ideal é aquela com menos cadeiras vazias.

O desafio

Você deve escrever um programa ou função que use um número inteiro e produza o arranjo ideal de cadeiras para esse número de alunos. O IO pode estar em qualquer formato razoável. Aqui está um exemplo de saída para qualquer número de alunos de 1 a 100:

1:  (1, 1)
2:  (1, 2)
3:  (2, 2)
4:  (2, 2)
5:  (2, 3)
6:  (2, 3)
7:  (3, 3)
8:  (3, 3)
9:  (3, 3)
10: (2, 5)
11: (3, 4)
12: (3, 4)
13: (4, 4)
14: (4, 4)
15: (4, 4)
16: (4, 4)
17: (3, 6)
18: (3, 6)
19: (4, 5)
20: (4, 5)
21: (3, 7)
22: (5, 5)
23: (5, 5)
24: (5, 5)
25: (5, 5)
26: (4, 7)
27: (4, 7)
28: (4, 7)
29: (5, 6)
30: (5, 6)
31: (4, 8)
32: (4, 8)
33: (6, 6)
34: (6, 6)
35: (6, 6)
36: (6, 6)
37: (5, 8)
38: (5, 8)
39: (5, 8)
40: (5, 8)
41: (6, 7)
42: (6, 7)
43: (5, 9)
44: (5, 9)
45: (5, 9)
46: (7, 7)
47: (7, 7)
48: (7, 7)
49: (7, 7)
50: (5, 10)
51: (6, 9)
52: (6, 9)
53: (6, 9)
54: (6, 9)
55: (7, 8)
56: (7, 8)
57: (6, 10)
58: (6, 10)
59: (6, 10)
60: (6, 10)
61: (8, 8)
62: (8, 8)
63: (8, 8)
64: (8, 8)
65: (6, 11)
66: (6, 11)
67: (7, 10)
68: (7, 10)
69: (7, 10)
70: (7, 10)
71: (8, 9)
72: (8, 9)
73: (7, 11)
74: (7, 11)
75: (7, 11)
76: (7, 11)
77: (7, 11)
78: (9, 9)
79: (9, 9)
80: (9, 9)
81: (9, 9)
82: (7, 12)
83: (7, 12)
84: (7, 12)
85: (8, 11)
86: (8, 11)
87: (8, 11)
88: (8, 11)
89: (9, 10)
90: (9, 10)
91: (7, 13)
92: (8, 12)
93: (8, 12)
94: (8, 12)
95: (8, 12)
96: (8, 12)
97: (10, 10)
98: (10, 10)
99: (10, 10)
100: (10, 10)

Como de costume, isso é código-golfe, então as brechas padrão se aplicam e o vencedor é a resposta mais curta em bytes.

Geléia , 16 15 14 bytes

÷RĊ,Rµạ/+PỤḢịZ

Experimente online! ou verifique todos os casos de teste .

Como funciona

÷RĊ,Rµạ/+PỤḢịZ  Main link. Argument: n

 R              Range; yield [1, ..., n].
÷               Divide n by each k in [1, ..., n].
  Ċ             Ceil; round the quotients up to the nearest integer.
    R           Range; yield [1, ..., n].
   ,            Pair; yield A := [[ ⌈n ÷ 1⌉, ..., ⌈n ÷ n⌉ ], [ 1, ..., n ]].
     µ          Begin a new, monadic chain. Argument: A
      ạ/        Reduce A by absolute difference.
                This yields [ |⌈n ÷ 1⌉ - 1|, ..., |⌈n ÷ n⌉ - n| ].
         P      Product; reduce A by multiplication.
                This yields [ ⌈n ÷ 1⌉ × 1, ..., ⌈n ÷ n⌉ × n].
       +        Add the results to left and right, element by element. This yields
                [ |⌈n ÷ 1⌉ - 1| + ⌈n ÷ 1⌉ × 1, ..., |⌈n ÷ n⌉ - n| + ⌈n ÷ n⌉ × n ].
          Ụ     Grade up; sort the indices of the list of sums by their values.
           Ḣ    Head; extract the first value, which corresponds to the smallest
                sum. Grading up is stable, so this selects the first index of all
                with the smallest sum in case of a tie. In this event, the first
                index will have the highest absolute difference of all indices
                with the smallest sum, meaning that it has the lowest product and,
                therefore, the lowest number of empty chairs.
             Z  Zip; transpose A's rows and columns.
                This yields [[ ⌈n ÷ 1⌉, 1 ], ..., [ ⌈n ÷ n⌉, n ]].
            ị   Retrieve the pair at that index.

Python 2, 68 bytes

lambda n:min((abs(~i-n/~i)+n/~i*~i,i+1,0-n/~i)for i in range(n))[1:]

Equivalente ao mais "óbvio":

lambda n:min([(i+1,0-n/~i)for i in range(n)],key=lambda(p,q):abs(p-q)+p*q)

Haskell, 65 bytes

f x=snd$minimum[((a*b+a-b,a*b),(b,a))|a<-[1..x],b<-[1..a],a*b>=x]

Exemplo de uso: map f [1..5]-> [(1,1),(1,2),(2,2),(2,2),(2,3)].

Passa por um loop externo ade 1até x(x -> número de alunos) e um loop interno bde 1até a. Mantém tudo (b,a)onde a*b>=xe constrói pares dos ((arrangement points,seats left), (b,a))quais seguem a ordem lexicográfica de que precisamos para encontrar o mínimo. Nota: aé sempre maior que b, portanto, não precisamos absde quadratura. Não há necessidade de subtrair xda pontuação "assentos restantes", porque apenas a ordem relativa é importante. Finalmente, removemos o par de pontos com snd.

Ruby, 64 bytes

->n{(1..n).map{|w|h=(n+w-1)/w;[(h-w).abs+h*w,w*h,w,h]}.min[2,3]}

Uma lambada que toma o número de pessoas como argumento e retorna uma matriz com largura e altura da solução ideal.

MATL , 18 bytes

:Gy/Xkvtd|yp+&X<Z)

Experimente online!

Explicação

:      % Implicit input number N. Range [1 2 ... N]
G      % Push N again
y      % Duplicate second-from-top: push [1 2 ... N] again
/Xk    % Divide and round up
v      % Vertically concatenate. Gives 2×N array of rectangle sizes
td|    % Duplicate. Absolute difference of each column
y      % Duplicate second-from-top: push 2×N array again
p      % Product of each column
+      % Sum absolute differences and products
&X<    % Arg min
Z)     % Use as column index into the 2×N array. Implicitly display

Javascript, 98 bytes

Meu primeiro código de golfe, então eu posto de qualquer maneira!

f=n=>{for(o=1/0,i=1;i<=n;i++)for(j=n;i*j>=n;j--)t=i*j-n+Math.abs(i-j),o>t&&(o=t,a=[i,j]);return a}

Inicialmente, meu oobjeto era vazio e eu verifiquei se o.aestava vazio, por isso foi um caso especial na primeira rodada. Mas eu encontrei o truque 1/0 na resposta do edc65 para inicializar a variável para o Infinito.

Pitão, 24 22 21 bytes

Edit : na chave de classificação, percebo que não há necessidade de encontrar o número de cadeiras vazias. É equivalente a marcar o número total de cadeiras. Isso me salvou 2 bytes.

h.m_+B*FbaFbm,d.EcQdS

Experimente online!

Matlab(174) (146)121

  function g(n),f=@(n,i)ceil(n/i);x=[];for i=1:n,x=[sortrows(x); f(n,i)*i-1/(f(n,i)*i)+abs(f(n,i)-i) i f(n,i)];end,x(1,2:3)

• truque 1: adicionei a quantia 1-1/length*widthcomo pontuação

• truque 2: calculei o number_students/lengthteto para a largura do retângulo, o limite superior é o quadrado, mas também o teto

• Tenho certeza de que pode ser jogado ainda mais ...

tente

Edit: referenciado aos comentários de @StewieGriffin.

Edição 2:

• 1e nsão constantes, não é necessário adicioná-las à pontuação geral.
• Uma função tem poucos bytes a menos que o programa independente stdin.
• Eu usei a técnica de classificação ascendente, mas economiza muitos bytes.

Edit 3: teste de desempenho.

Python 2, 64 bytes

lambda n:max((~-i*~min(i,n/i),0-n/i,-i)for i in range(-n,0))[1:]

Esta é uma amálgama da resposta Python do @ Lynn (de onde fiz o max(...)[1:]truque) e do algoritmo da minha resposta Julia (que permite uma implementação um pouco mais curta).

Teste em Ideone .

Julia, 61 59 55 53 52 bytes

/ =cld
n->[m=indmax([~i*~-max(i,n/i)for i=1:n]),n/m]

Experimente online!

Como funciona

O código é equivalente à seguinte versão não destruída, onde cldé a divisão do teto.

function chairs(n)
    m = indmin([(i + 1) * (max(i, cld(n, i)) - 1) for i in 1:n])
    return [m, cld(n, m)]
end

Para encontrar o arranjo ideal, é claramente suficiente examinar os pares [i, j] , onde 1 ≤ i ≤ n e j = ⌈n / i⌉ .

A pontuação para esse arranjo é | j - i | + (ij - n) , onde o segundo somatório é o número de cadeiras vazias. Em vez das pontuações reais, podemos comparar pontuações aumentadas por uma constante, como ij + | j - i | + 1 .

É suficiente considerar os pares [i, j] onde i ≤ j, pois os arranjos [i, j] e [j, i] são igualmente válidos. Lidamos com pares estritamente decrescentes definindo j = max (⌈n / i⌉, i) , o que garante que j ≥ ie produza uma pontuação abaixo do ideal se /n / i⌉ <i .

Como j - i ≥ 0 , temos ij + | j - i | + 1 = ij + j - i + 1 = (i + 1) × (j - 1) , que pode ser calculado em menos bytes de código.

Finalmente indmin/ indmaxfornece o índice m (e, portanto, o valor de i ) do arranjo ótimo, que é m por ⌈n / m⌉ . Os laços são quebrados pela primeira ocorrência, que corresponde ao valor mais baixo de i , portanto, o valor mais alto de j - i e, portanto, o valor mais baixo de ij - n (cadeiras vazias).

JavaScript (ES6) 74 78

Edite mantendo o resultado temporário como uma matriz em vez de 2 vars, emprestado da resposta de Thiht

n=>(z=>{for(x=0;y=-~(~-n/++x),x<=y;)(s=y-x+x*y-n)>=z||(z=s,r=[x,y])})()||r

Menos golfe

n=>{
  z = 1/0
  for (x=0; y=(n-1)/++x+1|0, x <= y; )
  {
    s = y-x+x*y-n;
    if (s<z)
      z=s, r=[x,y]
  }
  return r
}

Teste

f=n=>(z=>{for(x=0;y=-~(~-n/++x),x<=y;)(s=y-x+x*y-n)>=z||(z=s,r=[x,y])})()||r

out=x=>O.textContent+=x+'\n'

for(i=1;i<=100;i++)out(i+' :( '+f(i)+' )')

<pre id=O></pre>

PHP, 129 bytes

function f($i){$s=INF;for($x=1;$x<$i;$x++){if($s>$t=(abs($x-$e=ceil($i/$x))-$i+($e*$x))){$s=$t;$d[0]=$x;$d[1]=$e;}}var_dump($d);}

Ungolfed:

function f ($i){
    $s=INF;
    for($x=1; $x<$i; $x++){ // for every number less than the input
        if( $s > $t=( abs($x-$e=ceil($i/$x))-$i+($e*$x) ) ){ 
            // determine the other dimension, the score, and compare to the minimum score
            $s=$t;
            $d[0]=$x;
            $d[1]=$e;
        }
    }
    var_dump($d);
}

PHP, 104 bytes

O algoritmo que resolve esse problema é simples e provavelmente é usado por outras respostas em linguagens semelhantes ao PHP (JavaScript, fe):

• comece com um grande valor para a pontuação inicial; né grande o suficiente (onde nestá o valor de entrada); a pontuação do arranjo computado na primeira iteração ( 1, n) é (n-1)+0;
• itere para todos os valores de largura entre 1e n; calcule a altura mínima como ceil(n/width), calcule a pontuação do arranjo usando a fórmula fornecida na pergunta (ie abs(width - height) + (width * height - n)); se a pontuação for melhor do que a melhor pontuação anterior, lembre-se da largura, altura e nova pontuação; nos laços, use o valor de width * height - npara o arranjo atual e o melhor arranjo anterior para detectar o novo melhor arranjo;
• Isso é tudo.

Após o golfe, esse algoritmo produz algo parecido com este (incluído aqui para facilitar a leitura):

for($s=$h=$j=$n=$argv[$w=$i=1];$i<=$j;$j=ceil($n/++$i)
{$c=$j-$i+$i*$j-$n;if($c<$s||$c==$s&&$i*$j<$w*$h){$w=$i;$h=$j;$s=$c;}}
echo"$w,$h";

Ele usa 137 bytes (quando colocados em uma única linha) e está longe dos 104 bytes anunciados no título. Provavelmente, o código pode ser reduzido por outros 2-3 bytes, mas a grande fonte de aprimoramento está em outro lugar: nos detalhes do algoritmo.

O algoritmo revisado:

Existem vários lugares onde o algoritmo pode ser aprimorado removendo código inútil.

• não há necessidade de iterar a largura de 1para $n; para a velocidade, a largura ( $i) deve iterar entre 1e floor(sqrt($n))mas isto faz com que o código de ainda mais tempo, em vez de encurtando-o; mas se a largura não exceder sqrt($n), a altura mínima ( $j) sempre será maior que sqrt($n)(o produto deve ser pelo menos $n);
• a instrução anterior permite usar $i <= $j(largura <= altura) como condição de término para o loop; Desta forma, a largura irá iterar a partir 1de floor(sqrt($n))ea altura terá valores começando com $ne indo para ceil(sqrt($n))(não necessariamente todos eles);
• sabendo que a largura é sempre menor ou igual à altura, podemos saber que abs(width - height)é sempre height - width( $j-$i); 5 bytes salvos desta maneira;
• o valor de entrada $né usado no cálculo da pontuação (o número de assentos desocupados é width * height - n), mas não é necessário; a pontuação não precisa ser exibida, é calculada apenas para comparação dos arranjos; removendo - nda fórmula de pontuação, salvamos outros 3 bytes (o código PHP é -$n) sem perder nada;
• dadas as duas últimas afirmações, a fórmula da pontuação se torna height - width + width * height( $j-$i+$i*$j);
• em empates (a pontuação do acordo atual é igual à melhor pontuação anterior), as regras dizem usar o acordo com menos vagas livres; como a largura sempre aumenta e a altura sempre diminui, a height - widthparte da pontuação diminui a cada passo;
• se a pontuação atual for igual à melhor pontuação anterior, as afirmações anteriores nos dizem que o número de vagas livres do acordo atual é maior que o do melhor acordo anterior; isso significa que o melhor arranjo anterior vence o empate;
• como os empates são sempre conquistados pelo melhor arranjo anterior, um novo arranjo se torna o melhor melhor arranjo somente quando sua pontuação é menor que a melhor arranjo anterior; o código que verifica se há vínculos é inútil e pode ser removido ( ||$c==$s&&$i*$j<$w*$h- muitos bytes);
• devido à remoção da -$nfórmula da pontuação, a pontuação do primeiro arranjo ( 1x$n) é $n-1+1*$n(ie 2*$n-1); o valor inicial da melhor pontuação ( $s) pode ser qualquer valor maior ou igual a 2*$n; a primeira iteração tem uma pontuação melhor e se torna o melhor arranjo, permitindo que o algoritmo seja executado sem problemas de inicialização.

O novo código ( 104 bytes ), após a aplicação das melhorias descritas acima, é:

for($s=2*$j=$n=$argv[$i=1];$i<=$j;$j=ceil($n/++$i))
if($s>$c=$j-$i+$i*$j){$w=$i;$h=$j;$s=$c;}echo"$w,$h";

Está embrulhado aqui para facilitar a leitura. Anexe o código acima com o marcador PHP <?php(tecnicamente, ele não faz parte do código), coloque-o em um arquivo (digamos arrange-your-chairs.php) e execute-o com um número inteiro maior que zero como argumento. Ele exibirá a largura e a altura do arranjo computado, separadas por vírgula:

$ php arrange-your-chairs.php 1001
28,36

Outra solução (116 bytes)

Outra solução que usa um algoritmo diferente:

for($n=$argv[1];++$j<=$n;)for($i=0;++$i<=$j;)
if($n<=$k=$i*$j)$a["$i,$j"]=($j-$i+$k-$n)*$n+$k;asort($a);echo key($a);

Ele coloca todas as combinações de pelo menos $nassentos em uma lista associativa; a chave é a representação em texto do arranjo, o valor é a pontuação do arranjo. Em seguida, classifica a lista (crescente por valor) e obtém a chave da primeira entrada.

Mais um (115 bytes)

foreach(range(1,$m=$n=$argv[1])as$i)
if(($d=ceil($n/$i))<=$i&&$m>=$s=$i*$d-$n+$i-$d){$m=$s;$w=$d;$h=$i;}echo"$w,$h";

Esta é a versão PHP da resposta de @ Neil (JavaScript / ES6, 85 bytes).

Existem algumas diferenças visíveis devido aos recursos de cada idioma:

• a resposta JS gera uma matriz de nvalores (indefinidos) e depois usa suas chaves para iterar de 0para n-1; incrementa i( d=(n+i++)/i|0) para iterar de 1para n; a solução PHP não precisa ser incrementada; ele usa range()para gerar uma matriz e usa os valores gerados ( 1para n) para iterar;
• a resposta JS usa (n+i)/ie converte o valor para inteiro usando |0para obter o menor inteiro maior que n/i; a resposta do PHP resolve esse problema facilmente com a função PHP ceil(); O JavaScript também fornece, Math.ceil()mas usa 5 bytes a mais que a solução encontrada por Neil;
• O PHP fornece a função array_map()que é de alguma forma semelhante ao JS, Array.map()mas não ajuda aqui; sua sintaxe é detalhada, foreachproduz um código mais curto; é maior que o código JS;
• mesclar as atribuições nas condições usando ||não é possível no PHP porque não possui o operador vírgula; Traduzi a||b||cpara if(!a&&!b)centão, porque ae bsão comparações, neguei seus operadores (substituídos <por >=); isso também produz código maior que a versão JS;
• outros 23 bytes precisam ser adicionados apenas porque os nomes das variáveis ​​no PHP precisam ser prefixados por $.

As versões simples de todas as soluções e o conjunto de testes podem ser encontradas no Github .

JavaSCript (ES6), 83 bytes

n=>[...Array(m=n)].map((_,i)=>(d=(n+i++)/i|0)>i||(s=i*d-n+i-d)>m||(m=s,r=[d,i]))&&r

Julia, 87

Eu acho que este é um passo na direção de encontrar um função mágica para o problema:

f(i)=(i+n)÷(i+1)|>j->(j*i<n)+j
_=indmin([sqrt(n)<=i?i-f(i)*(1-i):2n for i=1:n])
_,f(_)

Olha apenas pares (i, j=(i+n)/(i+1))ou(i, j+1)

Oracle SQL 11.2, 173 bytes

SELECT MIN(x||','||y)KEEP(DENSE_RANK FIRST ORDER BY y-x+(y*x-:1))FROM(SELECT CEIL(LEVEL/:1)x,CEIL(MOD(LEVEL+.1,:1))y FROM DUAL CONNECT BY LEVEL<=:1*:1)WHERE x<=y AND:1<=x*y;

Sem golfe

SELECT MIN(x||','||y)KEEP(DENSE_RANK FIRST ORDER BY y-x+(y*x-:1))  -- Keeps the minimal score
FROM   (SELECT CEIL(LEVEL/:1)x,CEIL(MOD(LEVEL+.1,:1))y FROM DUAL CONNECT BY LEVEL<=:1*:1) -- Generate x,y combinations 
WHERE  x<=y AND :1<=x*y  -- Filters out wrong combinations

Q 58 bytes

{c@d?&/d:+/(-/;*/)@\:+c:{((b<a)?1b)#+(b:-_-x%a;a:1+!x)}x}

Lamba que calcula o custo mínimo para um determinado valor (x) e retorna uma sequência de dois valores (largura, altura)

Adicionar nome a esse lambda requer outros dois caracteres (ex f: {..} em vez de {..})

Teste

{..}'1+!100

onde {..} é a lambda. Leia como "aplica lambda a cada valor de 1 + primeiras 100 ints" (em outras palavras, a cada valor 1..100)

Gera

1 1
2 1
2 2
2 2
3 2
3 2
3 3
3 3
3 3
5 2
4 3
4 3
4 4
4 4
4 4
4 4
6 3
6 3
5 4
5 4
7 3
5 5
..

Explicação

O lamdba aninhado {((b<a)?1b)#+(b:-_-x%a;a:1+!x)}gera todos os pares candidatos (largura, altura) para cadeiras x como duas seqüências (w1 w2 w3 ..; h1 h2 h3 ..) (larguras e alturas). Leia da esquerda para a direita, mas avalia da direita para a esquerda

a:1+!x gera valores 1..x e atribui essa sequência a um

-_- é negar andar negar e implementar ceil (ceil não é um primitivo da linguagem)

b:-_-x%aaplica teto a cada valor de x dividido por qualquer item im a e atribui a sequência resultante a b. Em outras palavras, b é teto cada x divididoPor cada 1..x

+(b;a) retorna uma secuência composta pelas seq ae seq b, e depois a vira (o resultado é uma sequência de pares em que o par i contém o elemento i de ae o elemento i de b)

b<a compara item por item de bec, e gera uma segurança de valores lógicos (true = 1b para cada índice em que b [i]

s?xretorna a primeira posição do item x na sequência s. Com (b<a)?1bBuscamos 1b (valor verdadeiro) na sequência resultante da comparação be ae obtemos a primeira posição em que b

n#sleva n primeiros n itens de seq s. Queremos descartar pares duplicados, então paramos quando o primeiro item de um par <segundo item (por exemplo, considere 13,1, mas não 1,13).

Como efeito colateral, cada par da sequência resultante tem uma distância decrescente entre aeb (ex (13 1; 7 2; 5 3; 4 4)

O par candidato gerado pelo lambda aninhado é designado a c. Em seguida, invertemos c (obtém b, a novamente) e aplicamos duas funções a esse argumento: */multiplica e -/subtrai. O resultado (-/;*/)@\:+cé a diferença e o produto de cada par. +/é soma total e calcula o custo final. O custo de cada patir é atribuído a d

& / é mínimo, então &/d é o custo mínimo. Com d?&/dencontramos a primeira ocorrência de custo mínimo em d, e com c @ .. recuperamos o par nessa posição. Como cada par é distante decrescente entre a e n, o primeiro mínimo encontrado tem o máximo distante entre outros pares mínimos, então aplicamos a regra do empate corretamente