Вы обучаете класс студентов интересным предпочтениям относительно того, как устроены их стулья. У них есть 3 очень специфических требования к расположению стульев:

1. Большинство из них расположены в прямоугольнике, даже если некоторые стулья пустуют.

2. Должно быть как можно меньше пустых стульев.

3. Они должны быть как можно более квадратными. Прямоугольность определяется расстоянием между шириной и высотой прямоугольника, чем ниже, тем лучше. Например, прямоугольник 4x7имеет квадратность 3.

Чтобы быть более конкретным, «оценка» договоренности - это расстояние между шириной и высотой плюс количество стульев, которые опустели бы.

Давайте возьмем пример. Допустим, у вас 13 учеников. Вы можете расположить стулья любым из следующих способов:

1x13
2x7
3x5
4x4

1x13не очень квадратный На самом деле, 1 и 13 разнесены на 12, поэтому мы даем этому расположению 12 баллов. У него также 0 пустых стульев, поэтому мы добавляем 0 баллов, что дает этому расположению 12 баллов. Не так уж и здорово.

2x7конечно лучше. 2 и 7 разнесены только на 5, поэтому мы даем этому расположению 5 баллов. Однако, если вы на самом деле расположите 2 ряда по семь стульев, это займет 14 стульев, то есть один стул будет пустым. Таким образом, мы добавляем одно очко, давая этой договоренности оценку 6.

Мы могли бы также сделать 3x5. 3 и 5 - 2, так что +2 балла. Это займет 15 стульев, то есть у нас будет два дополнительных стула, так что еще +2 балла, для оценки 4.

Последний вариант 4x4. 4 и 4 - 0, поэтому мы даем это +0 баллов. 4x4 занимает 16 стульев, так что 3 стула пустуют, что дает общий балл 3. Это оптимальное решение.

В случае галстука оптимальным решением будет решение с менее пустыми стульями.

Соревнование

Вы должны написать программу или функцию, которая принимает целое число и выводит оптимальное расположение стульев для такого количества студентов. IO может быть в любом разумном формате. Вот пример вывода для любого количества студентов от 1 до 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)

Как обычно, это код-гольф, поэтому применяются стандартные лазейки, и победитель - самый короткий ответ в байтах.

Желе , 16 15 14 байт

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

Попробуйте онлайн! или проверьте все контрольные примеры .

Как это устроено

÷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 байт

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

Эквивалент более «очевидного»:

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

Haskell, 65 байт

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

Пример использования: map f [1..5] -> [(1,1),(1,2),(2,2),(2,2),(2,3)].

Проходит внешний цикл aот 1до x(х -> количество студентов) и внутренний цикл bот 1до a. Сохраняет все (b,a)где a*b>=xи строит пары, ((arrangement points,seats left), (b,a))которые следуют лексикографическому порядку, нам нужно найти минимум. Примечание: aвсегда больше чем b, поэтому нам не нужна absпрямоугольность. Не нужно вычитать xиз балла «осталось мест», потому что имеет значение только относительный порядок. Наконец мы удаляем пару очков с snd.

Рубин, 64 байта

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

Лямбада, которая принимает число людей в качестве аргумента и возвращает массив с шириной и высотой оптимального решения.

MATL , 18 байт

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

Попробуйте онлайн!

объяснение

:      % 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 байт

Мой первый код гольф, поэтому я все равно публикую!

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}

Первоначально my oбыл пустым объектом, и я проверил, o.aпусто ли это, поэтому это был особый случай в первом раунде. Но я нашел трюк 1/0 в ответе edc65, чтобы инициализировать переменную в бесконечность.

Pyth, 24 22 21 байт

Изменить : в ключе сортировки, я понимаю, что нет необходимости находить количество пустых стульев. Это эквивалентно общему количеству стульев. Это спасло мне 2 байта.

h.m_+B*FbaFbm,d.EcQdS

Попробуйте онлайн!

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)

• Трюк 1: я добавил сумму в 1-1/length*widthкачестве подсчета очков

• Трюк 2: я рассчитал number_students/lengthceiled для ширины прямоугольника, верхняя граница - квадрат, но тоже Ceiled

• Я уверен, что это может быть дальше в гольфе ...

попытайся

Изменить: ссылается на замечания @StewieGriffin.

Изменить 2:

• 1и nконстанты не нужно добавлять их в общий счет.
• Функция на несколько байтов меньше, чем стандартная программа stdin.
• Я использовал технику сортировки по возрастанию, она экономит слишком много байтов.

Редактировать 3: тест на производительность.

Python 2, 64 байта

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

Это объединение ответа @ Lynn's Python (откуда я взял max(...)[1:]трюк) и алгоритма из моего ответа Джулии (что позволяет немного более короткую реализацию).

Проверьте это на Ideone .

Юлия, 61 59 55 53 52 байта

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

Попробуйте онлайн!

Как это устроено

Код эквивалентен следующей версии без заглавных букв с cldразделением потолка.

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

Чтобы найти оптимальное расположение, явно достаточно изучить пары [i, j] , где 1 ≤ i ≤ n и j = ⌈n / i⌉ .

Оценка для такой договоренности составляет | j - i | + (ij - n) , где второе слагаемое - количество пустых стульев. Вместо фактических баллов мы можем сравнивать баллы, дополненные константой, например, ij + | j - i | + 1 .

Достаточно рассмотреть пары [i, j], где i ≤ j, поскольку схемы [i, j] и [j, i] одинаково верны. Мы имеем дело со строго нисходящими парами, устанавливая вместо этого j = max (⌈n / i⌉, i) , что гарантирует, что j ≥ i, и даст субоптимальный результат, если ⌈n / i⌉ <i .

Поскольку j - i ≥ 0 , имеем ij + | j - i | + 1 = ij + j - i + 1 = (i + 1) × (j - 1) , который может быть вычислен в меньшем количестве байтов кода.

Наконец, indmin/ indmaxдает индекс m (и, следовательно, значение i ) оптимального расположения, который равен m на ⌈n / m⌉ . Связи разрываются при первом появлении, которое соответствует наименьшему значению i , следовательно, наибольшему значению j - i и, следовательно, наименьшему значению ij - n (пустые стулья).

JavaScript (ES6) 74 78

Изменить, сохранив временный результат в виде массива вместо 2 переменных, заимствованных из ответа Тихта

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

Меньше гольфа

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
}

Тестовое задание

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 байт

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 байта

Алгоритм, решающий эту проблему, прост и, вероятно, используется другими ответами на языках, похожих на PHP (JavaScript, fe):

• начать с большого значения для начального счета; nдостаточно большой (гдеn входное значение); оценка расположения, вычисленная на первой итерации ( 1, n), равна (n-1)+0;
• итерация для всех значений ширины между 1и n; рассчитать минимальную высоту какceil(n/width) , вычислите оценку расположения, используя формулу, представленную в вопросе (то есть abs(width - height) + (width * height - n)); если результат лучше, чем предыдущий лучший результат, запомните ширину, высоту и новый лучший результат; используйте связи width * height - nдля текущей договоренности и предыдущей наилучшей договоренности, чтобы обнаружить новую наилучшую договоренность;
• это все.

После игры в гольф этот алгоритм производит что-то вроде этого (обернуто здесь для удобства чтения):

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";

Использует 137 байт. (при размещении в одной строке), и это далеко от 104 байтов, объявленных в заголовке. Код, вероятно, может быть сокращен еще на 2-3 байта, но большой источник улучшений находится где-то еще: в деталях алгоритма.

Пересмотренный алгоритм:

Есть несколько мест, где алгоритм может быть улучшен путем удаления ненужного кода.

• нет необходимости перебирать ширину от 1до $n; для скорости width ( $i) должна выполнять итерации между 1и, floor(sqrt($n))но это делает код еще длиннее, а не сокращает его; но если ширина не превышает sqrt($n), минимальная высота ( $j) всегда будет больше чем sqrt($n)(их произведение должно быть как минимум $n);
• предыдущий оператор позволяет использовать $i <= $j(width <= height) в качестве условия завершения цикла; таким образом, ширина будет повторяться от 1до, floor(sqrt($n))а высота получит значения, начинающиеся с $nи понижающиеся ceil(sqrt($n))(не обязательно все);
• зная, что ширина всегда меньше или равна высоте, мы знаем, что abs(width - height)всегда height - width( $j-$i); 5 байтов сохранены таким образом;
• входное значение $nиспользуется при подсчете очков (количество незанятых мест width * height - n), но это не нужно; оценка не должна отображаться, она рассчитывается только для сравнения договоренностей; удаляя - nиз формулы оценки, мы сохраняем еще 3 байта (код PHP -$n), ничего не теряя;
• учитывая последние два утверждения, формула оценки становится height - width + width * height( $j-$i+$i*$j);
• по связям (оценка текущей расстановки совпадает с предыдущей лучшей оценкой), правила говорят использовать расстановку с меньшим количеством свободных мест; поскольку ширина всегда увеличивается, а высота всегда уменьшается, height - widthчасть оценки уменьшается на каждом шаге;
• если текущий балл равен предыдущему лучшему баллу, предыдущие утверждения говорят нам, что количество свободных мест в текущем соглашении больше, чем в предыдущем лучшем соглашении; это означает, что предыдущая лучшая аранжировка выиграет ничью;
• поскольку связи всегда выигрывают по предыдущей лучшей договоренности, новая договоренность становится новой лучшей договоренностью, только когда ее оценка меньше, чем предыдущая лучшая; код, который проверяет наличие связей, бесполезен и может быть удален ( ||$c==$s&&$i*$j<$w*$h- много байтов);
• из-за удаления из -$nформулы оценки, оценка для первой договоренности ( 1x$n) равна $n-1+1*$n(т.е. 2*$n-1); начальное значение best score ( $s) может быть любым значением, большим или равным 2*$n; первая итерация имеет лучший результат, и она становится наилучшей схемой, позволяющей алгоритму работать без проблем инициализации.

Новый код ( 104 байта ) после применения описанных выше улучшений:

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";

Это обернуто здесь для удобочитаемости. Добавьте код выше с маркером PHP <?php(технически он не является частью кода), поместите его в файл (скажем arrange-your-chairs.php) и запустите с целым числом, большим нуля в качестве аргумента. Он будет отображать ширину и высоту вычисляемого расположения, разделенные запятой:

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

Другое решение (116 байт)

Другое решение, которое использует другой алгоритм:

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

Это помещает все комбинации по крайней мере $nмест в ассоциативный список; ключ - текстовое представление соглашения, значение - оценка соглашения. Затем он сортирует список (по возрастанию по значению) и получает ключ первой записи.

Еще один (115 байт)

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";

Это PHP-версия ответа @ Neil (JavaScript / ES6, 85 байт).

Есть некоторые заметные различия из-за особенностей каждого языка:

• ответ JS генерирует массив n(неопределенных) значений, а затем использует его ключи для итерации от 0до n-1; он увеличивает i( d=(n+i++)/i|0), чтобы сделать итерацию от 1до n; решение PHP не нужно увеличивать; он использует range()для генерации массива, а затем использует сгенерированные значения ( 1дляn ) для итерации;
• JS-ответ использует (n+i)/iзатем преобразует значение в целое число, используя, |0чтобы получить наименьшее целое число больше, чем n/i; ответ PHP решает эту проблему легко с помощью функции PHP ceil(); JavaScript также предоставляет, Math.ceil()но он использует на 5 байт больше, чем решение, найденное Нилом;
• PHP предоставляет функцию, array_map()которая чем-то похожа на JS, Array.map()но здесь она не помогает; его синтаксис многословен,foreach производит более короткий код; хотя он больше, чем код JS;
• объединение присваиваний в условия использования ||невозможно в PHP, поскольку в нем отсутствует оператор запятой; Я перевел a||b||cв if(!a&&!b)cтогда, потому что aи bявляются сравнениями, я отрицал их операторы (заменены <на >=); это также производит больший код, чем версия JS;
• еще 23 байта должны быть добавлены только потому, что имена переменных в PHP должны начинаться с префикса $.

Развернутые версии всех решений и наборов тестов можно найти на Github .

JavaSCript (ES6), 83 байта

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

Юлия, 87

Я думаю, что это один шаг в направлении к поиску волшебной функции для проблемы:

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(_)

Это смотрит только на пары (i, j=(i+n)/(i+1))или(i, j+1)

Oracle SQL 11.2, 173 байта

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;

Un-golfed

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 байт

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

Lamba, которая вычисляет минимальную стоимость для данного значения (x) и возвращает последовательность из двух значений (ширина, высота)

Добавление имени к этой лямбде требует двух других символов (например, f: {..} вместо {..})

Тестовое задание

{..}'1+!100

где {..} лямбда Читайте как «применяет лямбду к каждому значению 1 + первые 100 дюймов» (другими словами, к каждому значению 1..100)

Формирует

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

объяснение

Вложенная lamdba {((b<a)?1b)#+(b:-_-x%a;a:1+!x)}генерирует все пары кандидатов (widht, высота) для x стульев как две последовательности (w1 w2 w3 ..; h1 h2 h3 ..) (ширины и высоты). Читайте слева направо, но оценивает справа налево

a:1+!x генерирует значения 1..x и присваивает эту последовательность

-_- является отрицанием пола отрицанием, и реализует ceil (ceil не является примитивом языка)

b:-_-x%aприменяет ceil к каждому значению x, деленному на любой элемент im a, и присваивает результирующую последовательность b. Другими словами, каждый элемент x делится на 1.x

+(b;a) возвращает последовательность, состоящую из seq a и seq b, затем переворачивает ее (в результате получается последовательность пар, в которой i-pair содержит элемент i из a и элемент i из b)

b<a сравнивает элемент за элементом из b и a и генерирует последовательность логических значений (true = 1b для каждого индекса, где b [i]

s?xвозвращает первую позицию элемента x в последовательности s. С (b<a)?1bМы ищем 1b (истинное значение) в последовательности, полученной в результате сравнения b и a, и получаем первую позицию, где b

n#sберет n первых n элементов из последовательностей. Мы хотим отбросить дублирующиеся пары, поэтому мы останавливаемся, когда первый элемент пары <второй элемент (например, рассмотрим 13,1, но не 1,13).

Как побочный эффект, каждая пара получающейся последовательности имеет уменьшающееся расстояние между a и b (например, (13 1; 7 2; 5 3; 4 4)

Пара кандидатов, сгенерированная вложенной лямбдой, присваивается c. Затем мы переворачиваем c (снова получаем b, a) и применяем к этому аргументу две функции: */умножаем на и -/вычитаем на. Результатом (-/;*/)@\:+cявляется разница и произведение каждой пары.+/суммируется, и рассчитывается окончательная стоимость. Стоимость каждого патир назначается на д

& / является минимальным значением, поэтому &/d является минимальной стоимостью. С помощью d?&/dмы находим первое вхождение минимальной стоимости в d, а с помощью c @ .. мы получаем пару в этой позиции. Поскольку каждая пара имеет уменьшающееся расстояние между a и n, первый найденный минимум имеет максимальное расстояние между другими минимальными парами, поэтому мы правильно применяем правило связи