Jak powinieneś ustawić krzesła?

20

Uczysz klasę uczniów z interesującymi preferencjami dotyczącymi rozmieszczenia ich krzeseł. Istnieją 3 bardzo szczegółowe wymagania dotyczące rozmieszczenia krzeseł:

  1. Najczęściej są ułożone w prostokąt, nawet jeśli oznacza to, że niektóre krzesła są puste.

  2. Musi być jak najmniej pustych krzeseł.

  3. Muszą być możliwie „kwadratowe”. Kwadratowość zależy od odległości między szerokością a wysokością prostokąta, im niższa, tym lepiej. Na przykład prostokąt, który 4x7ma kwadratowość 3.

Mówiąc ściślej, „wynikiem” aranżacji jest odległość między szerokością a wysokością plus liczba krzeseł, które mogłyby zostać puste.

Weźmy przykład. Powiedzmy, że masz 13 uczniów. Krzesła można ustawić w dowolny z następujących sposobów:

1x13
2x7
3x5
4x4

1x13nie jest bardzo kwadratowy. W rzeczywistości 1 i 13 dzieli się na 12, więc dajemy temu układowi 12 punktów. Ma również 0 pustych krzeseł, więc dodajemy 0 punktów, co daje wynikowi 12 punktów. Niezbyt dobrze.

2x7jest z pewnością lepszy. 2 i 7 są tylko 5 od siebie, więc dajemy temu układowi 5 punktów. Jeśli jednak faktycznie ustawisz 2 rzędy po siedem krzeseł, zajmie to 14 krzeseł, co oznacza, że ​​jedno krzesło będzie puste. Dodajemy więc jeden punkt, co daje temu układowi wynik 6.

Możemy też zrobić 3x5. 3 i 5 to 2 osobno, więc +2 punkty. Zajmuje 15 krzeseł, co oznacza, że ​​mielibyśmy dwa dodatkowe krzesła, więc kolejne +2 punkty za wynik 4.

Ostatnia opcja, 4x4. 4 i 4 są od siebie równe 0, więc dajemy to +0 punktów. 4x4 zajmuje 16 krzeseł, więc 3 krzesła są puste, co daje łączny wynik 3. To optymalne rozwiązanie.

W przypadku remisu optymalnym rozwiązaniem jest rozwiązanie z mniej pustymi krzesłami.

Wyzwanie

Musisz napisać program lub funkcję, która przyjmuje liczbę całkowitą i wyświetla optymalne ustawienie krzeseł dla tej liczby uczniów. IO może mieć dowolny rozsądny format. Oto przykładowe wyniki dla dowolnej liczby uczniów od 1 do 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)

Jak zwykle jest to gra w golfa, więc obowiązują standardowe luki, a zwycięzca jest najkrótszą odpowiedzią w bajtach.

DJMcMayhem
źródło
Związane z.
Martin Ender

Odpowiedzi:

8

Galaretka , 16 15 14 bajtów

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

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

÷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.
Dennis
źródło
4

Python 2, 68 bajtów

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

Odpowiednik bardziej „oczywistego”:

lambda n:min([(i+1,0-n/~i)for i in range(n)],key=lambda(p,q):abs(p-q)+p*q)
Lynn
źródło
Możesz zaoszczędzić trzy bajty, iterując range(-n,0), tak jak ja w mojej odpowiedzi . Zestaw testowy.
Dennis
3

Haskell, 65 bajtów

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

Przykład użycia: map f [1..5]-> [(1,1),(1,2),(2,2),(2,2),(2,3)].

Przechodzi przez zewnętrzną pętlę aod 1do x(x -> liczba uczniów) i wewnętrzną pętlę bod 1do a. Przechowuje wszystko (b,a)gdzie a*b>=xi buduje pary ((arrangement points,seats left), (b,a))zgodnie z porządkiem leksykograficznym, musimy znaleźć minimum. Uwaga: azawsze jest większa niż b, więc nie potrzebujemy abskwadratowości. Nie trzeba odejmować wyniku xod „wolnych miejsc”, ponieważ liczy się tylko kolejność względna. Na koniec usuwamy parę wyników za pomocą snd.

nimi
źródło
Dlaczego nie tylko (a b + ab, (b, a))? Jeśli zminimalizujesz wynik, na pewno i tak zminimalizujesz b, czy coś mi brakuje?
justinpc
@jpcooper: a*b(liczba wolnych miejsc) to remis, jeśli główny wynik jest równy. Przykład n=43A) a=7, b=7, Wynik: (49,49)b) a=9, b=5, Wynik: (49,45). Główny wynik jest równy, decyduje remis, b) wygrywa.
nimi
Masz rację. Powinienem był lepiej przeczytać opis.
justinpc
@ jpcooper: poczekaj chwilę ... jeśli usunę remis a*b, same liczby, (b,a)które muszę nosić przy sobie, działają jak remis i dają takie same wyniki dla (przynajmniej) n=1..300. Produkt jest mały, jeśli jeden z czynników (tutaj b) jest mały. Ale dopóki nie mam formalnego dowodu, nie chcę tego faktu używać. Zobaczmy, czy go znajdę.
nimi
Słuszna uwaga. Wydaje się słuszne i nie powinno być zbyt trudne wymyślić dowód. Zaczynam się zastanawiać, czy może być liniowe rozwiązanie tego problemu.
justinpc
2

Rubinowy, 64 bajty

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

Lambada, która przyjmuje liczbę ludzi jako argument i zwraca tablicę o szerokości i wysokości optymalnego rozwiązania.

MegaTom
źródło
Dlaczego potrzebujesz w*hjako drugiego elementu w tablicy? Nie wydaje mi się, żeby szczególnie to zmieniało, kiedy dzwonisz, minponieważ minimalizujesz wynik, czyli pierwszy element.
Wartość tuszu
@ KevinLau-notKenny z pytania:In case of a tie, the optimal solution is the one with less empty chairs
MegaTom
2

MATL , 18 bajtów

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

Wypróbuj online!

Wyjaśnienie

:      % 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
Luis Mendo
źródło
2

JavaScript, 98 bajtów

Mój pierwszy golf golfowy, więc i tak publikuję!

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}

Początkowo mój obył pustym przedmiotem i sprawdziłem, czy o.abył pusty, więc był to szczególny przypadek w pierwszej rundzie. Ale znalazłem sztuczkę 1/0 w odpowiedzi edc65, aby zainicjować zmienną na Infinity.

Thiht
źródło
I spróbuję użyć sztuczki, aby użyć obiektu do przechowywania tymczasowego wyniku
edc65
1

Pyth, 24 22 21 bajtów

Edycja : w kluczu sortującym zdaję sobie sprawę, że nie ma potrzeby znajdowania liczby pustych krzeseł. Odpowiada to całkowitej liczbie krzeseł. To zaoszczędziło mi 2 bajty.

h.m_+B*FbaFbm,d.EcQdS

Wypróbuj online!

Leaky Nun
źródło
1

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)
  • sztuczka 1: dodałem kwotę 1-1/length*widthjako remis

  • sztuczka 2: obliczyłem number_students/lengthpułap dla szerokości prostokąta, górna granica to kwadrat, ale też sufit

  • Jestem pewien, że można dalej grać w golfa ...

Spróbuj


Edycja: odniesienie do uwag @StewieGriffin.

Edycja 2:

  • 1i nsą stałymi, których nie trzeba dodawać do ogólnego wyniku.
  • Funkcja jest o kilka bajtów mniejsza niż samodzielny program stdin.
  • Użyłem techniki sortowania ascendent, która oszczędza jednak zbyt wiele bajtów.

Edycja 3: test wydajności.

Abr001am
źródło
@StewieGriffin, który nie jest dużym problemem, można go rozwiązać za pomocąunique
Abr001am
1
myślę, że jestem w połowie drogi do jakiegoś fajnego tłumaczenia matematycznego tego problemu, ale nadal pozostaje
hipotezą
Myślałem również o tym. Zobacz przykład Julii.
mschauer
1

Julia, 61 59 55 53 52 bajty

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

Wypróbuj online!

Jak to działa

Kod jest równoważny z następującą wersją bez golfa, w której cldpodział sufitu.

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

Aby znaleźć optymalne ustawienie, wystarczy wyraźnie zbadać pary [i, j] , gdzie 1 ≤ i ≤ n oraz j = ⌈n / i⌉ .

Wynik takiego układu wynosi | j - i | + (ij - n) , gdzie drugim summand jest liczba pustych krzeseł. Zamiast faktycznych wyników, możemy porównać wyniki powiększone o stałą, taką jak ij + | j - i | + 1 .

Wystarczy wziąć pod uwagę pary [i, j] gdzie i ≤ j, ponieważ ustalenia [i, j] i [j, i] są jednakowo ważne. Mamy do czynienia z ściśle malejącymi parami, ustawiając zamiast tego j = max (⌈n / i⌉, i) , co zapewnia, że j ≥ i da wynik nieoptymalny, jeśli ⌈n / i⌉ <i .

Ponieważ j - i ≥ 0 , mamy ij + | j - i | + 1 = ij + j - i + 1 = (i + 1) × (j - 1) , które można obliczyć w mniejszej liczbie bajtów kodu.

Na koniec indmin/ indmaxpodaje wskaźnik m (a zatem wartość i ) optymalnego układu, który wynosi m o ⌈n / m⌉ . Więzy są zrywane przy pierwszym wystąpieniu, które odpowiada najniższej wartości i , a zatem najwyższej wartości j - i, a tym samym najniższej wartości ij - n (puste krzesła).

Dennis
źródło
1

JavaScript (ES6) 74 78

Edytować zachowując wynik temp jako tablicę zamiast 2 zmiennych, zapożyczoną z odpowiedzi Thiht

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

Mniej golfa

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
}

Test

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>

edc65
źródło
1

PHP, 129 bajtów

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

Nie golfowany:

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);
}
Business Cat
źródło
1

PHP, 104 bajty

Algorytm rozwiązujący ten problem jest prosty i prawdopodobnie jest używany przez inne odpowiedzi w językach podobnych do PHP (JavaScript, fe):

  • zacznij od dużej wartości dla początkowego wyniku; njest wystarczająco duży (gdzie njest wartość wejściowa); wynik aranżacji obliczony przy pierwszej iteracji ( 1, n) wynosi (n-1)+0;
  • iteruj dla wszystkich wartości szerokości między 1i n; obliczyć minimalną wysokość jako ceil(n/width), obliczyć wynik aranżacji za pomocą wzoru podanego w pytaniu (tjabs(width - height) + (width * height - n) ); jeśli wynik jest lepszy niż poprzedni najlepszy wynik, pamiętaj o szerokości, wysokości i nowym najlepszym wyniku; w przypadku powiązań użyj wartości width * height - ndla bieżącego uzgodnienia i poprzedniego najlepszego uzgodnienia w celu wykrycia nowego najlepszego uzgodnienia;
  • to wszystko.

Po grze w golfa ten algorytm tworzy coś takiego (zawinięte tutaj dla czytelności):

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

Używa 137 bajtów (po umieszczeniu w jednym wierszu) i dalekie jest od 104 bajtów podanych w tytule. Kod można prawdopodobnie skrócić o kolejne 2-3 bajty, ale dużym źródłem usprawnień jest gdzie indziej: w szczegółach algorytmu.

Zmieniony algorytm:

Istnieje kilka miejsc, w których algorytm można ulepszyć, usuwając niepotrzebny kod.

  • nie ma potrzeby powtarzania szerokości od 1do$n ; dla prędkości, szerokość ( $i) musi się powtarzać między 1afloor(sqrt($n)) , ale to sprawia, że nawet dłużej kod zamiast skrócenia go; ale jeśli szerokość nie przekraczasqrt($n) , minimalna wysokość ( $j) zawsze będzie większa niż sqrt($n)(ich iloczyn musi wynosić co najmniej $n);
  • poprzednie oświadczenie pozwala na użycie $i <= $j (szerokość <= wysokość) jako warunku zakończenia pętli; w ten sposób szerokość będzie iterować1 do, floor(sqrt($n))a wysokość uzyska wartości zaczynające się $ni schodzące do ceil(sqrt($n))(niekoniecznie wszystkie);
  • wiedząc, że szerokość jest zawsze mniejsza lub równa wysokości, daj nam znać, że abs(width - height)jest zawsze height - width( $j-$i); 5 bajtów zapisanych w ten sposób;
  • wartość wejściowa $njest używana do obliczania wyniku (liczba wolnych miejsc jest równa width * height - n), ale nie jest potrzebna; wynik nie musi być wyświetlany, jest obliczany tylko w celu porównania rozwiązań; usuwając - nze wzoru wyniku zapisujemy kolejne 3 bajty (kod PHP jest -$n), nie tracąc nic;
  • biorąc pod uwagę dwa ostatnie stwierdzenia, formuła punktacji staje się height - width + width * height($j-$i+$i*$j );
  • w przypadku remisów (wynik bieżącego układu jest taki sam, jak poprzedni najlepszy wynik), zasady mówią, aby używać układu z mniejszą liczbą wolnych miejsc; ponieważ szerokość zawsze rośnie, a wysokość zawsze maleje,height - width część wyniku maleje z każdym krokiem;
  • jeżeli bieżący wynik jest równy poprzedniemu najlepszemu wynikowi, poprzednie stwierdzenia mówią nam, że liczba wolnych miejsc w bieżącym układzie jest większa niż w poprzednim najlepszym układzie; oznacza to, że poprzedni najlepszy układ wygrywa remis;
  • ponieważ remisy są zawsze wygrywane w poprzednim najlepszym układzie, nowy układ staje się nowym najlepszym układem tylko wtedy, gdy jego wynik jest mniejszy niż poprzedni najlepszy; kod sprawdzający powiązania jest bezużyteczny i można go usunąć (||$c==$s&&$i*$j<$w*$h - dużo bajtów);
  • z powodu usunięcia -$nze wzoru partytury, ocena dla pierwszego układu ( 1x$n) wynosi $n-1+1*$n(tj. 2*$n-1); początkowa wartość najlepszego wyniku ( $s) może być dowolną wartością większą lub równą 2*$n; pierwsza iteracja ma lepszy wynik i staje się najlepszym rozwiązaniem pozwalającym algorytmowi działać bez problemów z inicjalizacją.

Nowy kod ( 104 bajty ) po zastosowaniu opisanych powyżej ulepszeń to:

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

Jest on zawinięty tutaj dla czytelności. Przygotuj powyższy kod za pomocą znacznika PHP <?php(technicznie nie jest to część kodu), umieść go w pliku (powiedzmy arrange-your-chairs.php) i uruchom jako argument jako liczbę całkowitą większą niż zero. Wyświetli szerokość i wysokość obliczonego układu, oddzielone przecinkiem:

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

Inne rozwiązanie (116 bajtów)

Inne rozwiązanie wykorzystujące inny algorytm:

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

Zawiera wszystkie kombinacje przynajmniej $n miejsc na liście asocjacyjnej; kluczem jest tekstowa reprezentacja aranżacji, wartość to wynik aranżacji. Następnie sortuje listę (rosnąco według wartości) i otrzymuje klucz pierwszego wpisu.

Jeszcze jeden (115 bajtów)

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

To jest wersja PHP @ Neila odpowiedź (JavaScript / ES6, 85 bajtów).

Istnieją pewne zauważalne różnice związane z funkcjami każdego języka:

  • odpowiedź JS generuje tablicę n(niezdefiniowanych) wartości, a następnie używa swoich kluczy do iteracji od 0do n-1; inkrementuje i( d=(n+i++)/i|0), aby iterować od 1do n; rozwiązanie PHP nie musi zwiększać; używa range()do generowania tablicy, a następnie wykorzystuje wygenerowane wartości ( 1don ) do iteracji;
  • odpowiedź JS używa (n+i)/inastępnie konwertuje wartość na liczbę całkowitą, |0aby uzyskać najmniejszą liczbę całkowitą większą niż n/i; odpowiedź PHP rozwiązuje ten problem łatwo dzięki funkcji PHP ceil(); JavaScript zapewnia równieżMath.ceil() ale zużywa 5 bajtów więcej niż rozwiązanie znalezione przez Neila;
  • PHP zapewnia funkcję array_map()podobną do JS, Array.map()ale tutaj nie pomaga; jego składnia jest pełna, foreachtworzy krótszy kod; jest jednak większy niż kod JS;
  • scalanie przypisań do warunków przy użyciu ||nie jest możliwe w PHP, ponieważ brakuje operatora przecinka; Przetłumaczyłem a||b||cna if(!a&&!b)cto, ponieważ ai bsą porównania, zanegowałem ich operatorów (zastąpionych <przez >=); powoduje to również większy kod niż wersja JS;
  • należy dodać kolejne 23 bajty tylko dlatego, że nazwy zmiennych w PHP muszą być poprzedzone znakiem $.

Niegolfowane wersje wszystkich rozwiązań i pakietu testowego można znaleźć na Github .

aksjomat
źródło
1
To najdokładniejsza odpowiedź na kod-golf, jaką kiedykolwiek widziałem.
DJMcMayhem
0

JavaSCript (ES6), 83 bajty

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
Neil
źródło
Może mógłbyś zastosować moją sztuczkę (aby zaoszczędzić 2 bajty)
Leaky Nun
@KennyLau Nie sądzę, że to pomaga; Musiałbym zwiększyć, mżeby to zrekompensować.
Neil,
0

Julia, 87 lat

Myślę, że jest to jeden krok w kierunku znalezienia magicznej funkcji dla problemu:

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

Patrzy tylko na pary (i, j=(i+n)/(i+1))lub(i, j+1)

mschauer
źródło
proszę wyjaśnij dalej, jak to działa,
okazałeś
2
Nie jestem pewien, jak to ma działać. nNigdzie nie definiujesz i nie wydajesz się brać wkładu.
Dennis
Ach, przepraszam, właśnie wziąłem njako wkład. Trzeba by było to owinąć n->.... Fajnie, że mogłeś sprawić, że to zadziała.
mschauer
0

Oracle SQL 11.2, 173 bajtów

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;

Nie grał w golfa

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
Jeto
źródło
0

Q 58 bajtów

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

Lamba, która oblicza minimalny koszt dla danej wartości (x) i zwraca ciąg dwóch wartości (szerokość, wysokość)

Dodanie nazwy do tej lambdy wymaga dwóch innych znaków (np. F .: {..} zamiast {..})

Test

{..}'1+!100

gdzie {..} jest lambda. Odczytuje jako „stosuje lambda do każdej wartości 1 + pierwszych 100 ints” (innymi słowy do każdej wartości 1..100)

Generuje

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

Wyjaśnienie

Zagnieżdżona lamdba {((b<a)?1b)#+(b:-_-x%a;a:1+!x)}generuje wszystkie pary kandydatów (szerokość, wysokość) dla x krzeseł w dwóch sekwencjach (w1 w2 w3 ..; h1 h2 h3 ..) (szerokości i wysokości). Czytaj od lewej do prawej, ale ocenia od prawej do lewej

a:1+!x generuje wartości 1..x i przypisuje tę sekwencję do

-_- to negate floor negate i implementuje ceil (ceil nie jest prymitywem języka)

b:-_-x%astosuje pułap do każdej wartości x podzielonej przez dowolny element im a i przypisuje wynikową sekwencję do b. Innymi słowy, b oznacza pułap każdy x podzielony przez każdy 1..x

+(b;a) zwraca sekwencję złożoną z sekw. a i sek. b, a następnie odwraca ją (wynikiem jest sekwencja pary, w której i-para zawiera element i elementu a oraz element i elementu b)

b<a porównuje pozycję po pozycji b i a, i generuje sekwencję wartości logicznych (true = 1b dla każdego indeksu, gdzie b [i]

s?xzwraca pierwszą pozycję elementu x w sekwencji s. Z (b<a)?1bPoszukujemy 1b (wartości rzeczywistej) w sekwencji wynikającej z porównania b i a, i otrzymujemy pierwszą pozycję, gdzie b

n#spobiera n pierwszych n elementów z sekwencji. Chcemy odrzucić zduplikowane pary, więc zatrzymujemy się, gdy pierwszy element pary <drugi przedmiot (np. Rozważmy 13,1, ale nie 1,13).

Jako efekt uboczny każda para wynikowej sekwencji ma malejącą odległość między aib (np. (13 1; 7 2; 5 3; 4 4)

Para kandydatów wygenerowana przez zagnieżdżoną lambda jest przypisana do c. Następnie odwracamy c (ponownie uzyskuje b, a) i stosuje do tego argumentu dwie funkcje: */mnoży i -/odejmuje. Wynikiem (-/;*/)@\:+cjest różnica i iloczyn każdej pary.+/jest sumą i oblicza koszt końcowy. Koszt każdego patiru przypisany jest do d

i / to minimum, więc &/d to minimalny koszt. Za pomocą d?&/dznajdujemy pierwsze wystąpienie minimalnego kosztu w d, a za pomocą c @ .. odzyskujemy parę w tej pozycji. Ponieważ każda para ma malejącą odległość między a i n, pierwsze znalezione minimum ma maksymalną odległość między innymi parami minimalnymi, więc poprawnie stosujemy regułę remisu

J. Sendra
źródło