^{Wpis w piaskownicy (usunięty)}

Stare formacje armii rzymskiej są bardzo znane na całym świecie. W tych formacjach rzymscy legioniści zgrupowani w geometryczny kształt (zwykle prostokąt) chronią boki i ich większą część za pomocą swoich tarcz. Legioniści w pozycjach wewnętrznych zakrywali górną część, umieszczając tarczę nad głowami, legioniści na bokach nosili 2 lub więcej tarcz: jedną do ochrony części nadrzędnej i jedną lub więcej tarcz do ochrony boków (jeśli ktoś był w kącie miał 3 tarcze, jeśli ktoś był sam w formacji, miał 5 tarcz ^{Tak, wiem, że człowiek nie może nosić 5 tarcz, ale jakoś to zrobił} ). Korzystając z tej formacji, wszyscy rzymscy legioniści bronili się i byli wówczas najtrudniejszym przeciwnikiem.

Historia mówi, że był rzymski generał, który stwierdził, że najlepszym kształtem formacji był kwadrat (ta sama liczba legionistów w rzędach i kolumnach). Problem polegał na ustaleniu, ile formacji (i ich rozmiar) powinien podzielić swoją armię, aby:

• Nie pozostawiaj żadnego legionisty poza formacją (chociaż przyznał się do jednej formacji legionowej)
• Zmniejsz liczbę wymaganych osłon

Generał, po wykonaniu pewnych obliczeń matematycznych i obliczeń, doszedł do wniosku, że najlepszym sposobem na spełnienie tych 2 warunków jest rozpoczęcie od największego możliwego kwadratu, a następnie powtarzanie, dopóki legioniści nie opuścili .

---

Przykład:

Jeśli 35 legionistów w jego armii składało się z formacji

• Kwadrat legionistów 5 x 5 (jest to największy możliwy kwadrat).

Z pozostałymi legionistami (10)

• Kwadrat 3 x 3

Z pozostałymi legionistami (1)

• Kwadrat 1x1.

Na koniec będzie wyglądać mniej więcej tak:

   5x5      
* * * * *        3x3            
* * * * *       * * *      1x1  
* * * * *       * * *       *
* * * * *       * * *       
* * * * *               

Legioniści w pozycjach wewnętrznych zakrywali górną część, umieszczając tarczę nad głowami . Potrzebowali tylko 1 tarczy.

* * * * *                   
* 1 1 1 *       * * *       
* 1 1 1 *       * 1 *       *
* 1 1 1 *       * * *       
* * * * *               

Legioniści na flankach nosili 2

* 2 2 2 *                   
2 1 1 1 2       * 2 *       
2 1 1 1 2       2 1 2       *
2 1 1 1 2       * 2 *       
* 2 2 2 *               

Jeśli ktoś był w kącie, miał 3 tarcze

3 2 2 2 3               
2 1 1 1 2       3 2 3       
2 1 1 1 2       2 1 2       *
2 1 1 1 2       3 2 3       
3 2 2 2 3               

Jeśli ktoś był sam w formacji, miał 5 tarcz

3 2 2 2 3               
2 1 1 1 2       3 2 3       
2 1 1 1 2       2 1 2       5
2 1 1 1 2       3 2 3       
3 2 2 2 3               

Ta formacja wymagała łącznie 71 tarcz.

---

Wyzwanie

• Oblicz liczbę tarcz potrzebnych dla X legionistów

Wkład

• Liczba legionistów w armii

Wydajność

• Potrzebna ilość osłon.

Przypadki testowe

35 => 71
20 => 44
10 => 26
32 => 72

---

• Obowiązują standardowe zasady gry w golfa

Python 2 , 60 50 48 bajtów

def f(s):n=s**.5//1;return s and(n+4)*n+f(s-n*n)

Wypróbuj online!

Nowy w golfie kodowym, ale daje z siebie wszystko!

Metoda:

Suma, n^2 + 4ngdzie njest każdą z największych liczb kwadratowych, które sumują się do danych wejściowych.

Edytuj 1

Zmniejszony do 50 bajtów dzięki @Jonathan Frech!

Edytuj 2

Przełączono int(s**.5)na, s**.5//1aby zapisać 2 bajty dzięki @ovs

R , 51 50 bajtów

f=function(x,y=x^.5%/%1)"if"(x,y^2+4*y+f(x-y^2),0)

Wypróbuj online!

Kwadrat o długości boku musi mieć dokładnie tarczę . Zmniejszamy o największy kwadrat mniejszy lub równy aż wyniesie zero, kumulując liczbę tarcz wraz z upływem czasu.$y$$y^2+4y$$x$$x$

Dowód:

Biorąc pod uwagę idealny kwadrat o długości boku , potrzebujemy dokładnie 1 tarczy dla każdego członka kwadratu. Następnie dla każdego członka na krawędzi potrzebujemy dodatkowej tarczy. Istnieje użytkowników nie na brzegach, tak, że są użytkowników na krawędziach. Wreszcie dla każdego rogu potrzebujemy dodatkowej tarczy. Oprócz przypadku, gdy , możemy w ten sposób dodać 4. Upraszcza to co na szczęście daje również prawidłową wartość gdy , co pozwala nam używać go przez cały .$y$$(y-2)^2$$y^2-(y-2)^2$$y=1$$y^2+4y$$5$$y=1$$y$

JavaScript (ES7), 34 bajty

f=n=>n&&(w=n**.5|0)*w+w*4+f(n-w*w)

Wypróbuj online!

W jaki sposób?

$w = \lfloor\sqrt{n}\rfloor$$s_w$

$$s_w = w^2+4w$$

Na przykład dla :$w=3$

$$\begin{align}&\pmatrix{3 & 2 & 3\\2 & 1 & 2\\3 & 2 & 3}=&(s_3=21)\\&\pmatrix{1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1}+&(3^²=9)\\&\pmatrix{1 & 1 & 1\\0 & 0 & 0\\0 & 0 & 0}+\pmatrix{0 & 0 & 1\\0 & 0 & 1\\0 & 0 & 1}+\pmatrix{0 & 0 & 0\\0 & 0 & 0\\1 & 1 & 1}+\pmatrix{1 & 0 & 0\\1 & 0 & 0\\1 & 0 & 0}&(4\times3=12)\end{align}$$

Formuła obowiązuje dla , ponieważ .s 1 = $w=1$$s_1=5$

Galaretka , 13 bajtów

ƽ²ạƊƬ_Ɲ½ẋ4S+

Wypróbuj online!

-1 dzięki Jonathan Allan .

Julia 0.6 , 36 bajtów

!n=(s=isqrt(n))*s+4s+(n>0&&!(n-s*s))

Wypróbuj online!

Używa tej samej metody , co odpowiedź R @ Giuseppe, chociaż moja metoda dotarcia tam wymagała mniej znaczącego myślenia i bardziej tylko kontroli wzrokowej: wewnętrzny kwadrat 1s ma wymiary o , więc ma tarcze. Wokół tego znajdują się 4 ściany żołnierzy każda, każda z 2 tarczami - co dodaje tarcze. Wreszcie, są cztery 3 w czterech rogach, więc dodaje 12 tarcz.$n^2 + 4n$$(n - 2)$$(n - 2)$$(n - 2)^2$$n - 2$$4*(n - 2)*2$

$$(n-2)^2 + 4*(n-2)*2 + 4*3 = n^2 + 4 - 4n + 8n - 16 + 12 = n^2 + 4n$$

Nie golfowany:

!n = begin       # Assign to ! operator to save bytes on function parantheses
  s = isqrt(n)   # Integer square root: the largest integer m such that m*m <= n
  s * s +
    4 * s +
      (n > 0 &&  # evaluates to false = 0 when n = 0, otherwise recurses
        !(n - s * s))
end

(Można to również zrobić w 35 bajtach n>0?(s=isqrt(n))*s+4s+f(n-s*s):0, ale napisałem to dla Julii 0.7 chciałem uniknąć nowych ostrzeżeń o wycofaniu (wymagające spacji są ?i :).)

Stax , 15 bajtów

ëñ|^○╖?║<l╛P╝z√

Uruchom i debuguj

Brachylog , 26 bajtów

0|⟧^₂ᵐ∋N&;N-ℕ↰R∧N√ȧ×₄;N,R+

Wypróbuj online!

0           % The output is 0 if input is 0
|           % Otherwise,
⟧           % Form decreasing range from input I to 0
^₂ᵐ         % Get the squares of each of those numbers
∋N          % There is a number N in that list
&;N-ℕ       % With I - N being a natural number >= 0 i.e. N <= I
            % Since we formed a decreasing range, this will find the largest such number
↰           % Call this predicate recursively with that difference I - N as the input
R           % Let the result of that be R
∧N√ȧ        % Get the positive square root of N
×₄          % Multiply by 4
;N,R+       % Add N and R to that
            % The result is the (implicit) output

Retina 0.8.2 , 28 bajtów

.+
$*
(\G1|11\1)+
$&11$1$1
.

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

.+
$*

Konwertuj na dziesiętny.

(\G1|11\1)+

Dopasuj liczby nieparzyste. Pierwsze przejście przez grupę \1jeszcze nie istnieje, więc \G1można dopasować tylko , które pasują 1. Kolejne mecze nie mogą się zgadzać, \G1ponieważ \Gtylko dopasowania na początku meczu, więc zamiast tego musimy dopasować, 11\1który jest o 2 większy niż poprzedni mecz. Dopasowujemy jak najwięcej liczb nieparzystych, jak to możliwe, a zatem całkowite dopasowanie jest liczbą kwadratową, podczas gdy ostatni chwyt jest o jeden mniej niż dwa razy większy od jego boku.

$&11$1$1

Dodaj boczne osłony do każdego meczu. $&jest i wynosi podczas gdy potrzebujemy . 2 n - 1 n 2 + 4 n = n 2 + 2 + 2 ( 2 n - 1 $n^2$$1$2n-1$$n^2+4n=n^2+2+2(2n-1)$

.

Suma i przeliczenie na dziesiętne.

05AB1E , 17 bajtów

[Ð_#tïÐns4*+Šn-}O

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Obejście, ponieważ ΔDtïÐns4*+Šn-}O( 15 bajtów ) wydaje się nie działać. Wypróbuj online w trybie debugowania, aby zobaczyć, co mam na myśli. Spodziewam się, że aby przejść od [45,'35',25]do [45,10]po -i następnej iteracji Δ, ale najwyraźniej to czyści stos z wyjątkiem ostatniej wartości i staje się [10], w wyniku czego 0 na samym końcu .. Nie wiem, czy to ma zachowanie lub błąd .. (EDYCJA: Jest zamierzone, patrz na dole).

Wyjaśnienie:

Używa również gdzie jest szerokością w pętli, jak większość innych odpowiedzi.$w^2+4w$$w$

[        }     # Start an infinite loop:
 Ð             #  Triplicate the value at the top of the stack
  _#           #  If the top is 0: break the infinite loop
 t             #  Take the square-root of the value
               #   i.e. 35 → 5.916...
  ï            #  Remove any digits by casting it to an integer, so we have our width
               #   i.e. 5.916... → 5
   Ð           #  Triplicate that width
    n          #  Take the square of it
               #   i.e. 5 → 25
     s         #  Swap so the width is at the top again
      4*       #  Multiply the width by 4
               #   i.e. 5 → 20
        +      #  And sum them together
               #   i.e. 25 + 20 → 45
 Š             #  Triple-swap so the calculated value for the current width
               #  is now at the back of the stack
               #   i.e. [35,5,45] → [45,35,5]
  n            #  Take the square of the width again
               #   5 → 25
   -           #  Subtract the square of the width from the value for the next iteration
               #   i.e. 35 - 25 → 10
          O    # Take the sum of the stack
               #   i.e. [45,21,5,0,0] → 71

---

EDYCJA: Najwyraźniej zachowanie, które opisałem powyżej, Δjest zamierzone. Oto dwie 17-bajtowe alternatywy dostarczone przez @ Mr.Xcoder , które wykorzystują Δumieszczając wartości w tablicy global_array (with ^) i odzyskując je później (with ¯):

ΔЈtïnα}¯¥ÄDt··+O

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

ΔЈtïnα}¯¥ÄtD4+*O

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

dc , 25 bajtów

d[dvddSa*-d0<MLa+]dsMx4*+

Wypróbuj online!

Oblicza tarcze jako sum(n^2)(oryginalny numer) plus 4*sum(n), wciskając kopię każdej kwadratowej długości boku do rejestru stosu a, a następnie dodając wszystkie wartości z rejestru, agdy rekurencja „rozwija się”.

Łuska , 17 bajtów

ṁS+o*4√Ẋ≠U¡S≠(□⌊√

Wypróbuj online!

Alternatywny

ṁS*+4m√Ẋ≠U¡S≠(□⌊√

Wypróbuj online!

APL (Dyalog Unicode) , 31 30 bajtów

{⍵<2:⍵×5⋄(S×S+4)+∇⍵-×⍨S←⌊⍵*.5}

Wypróbuj online!

-1 bajt dzięki @jslip

Rubinowy , 45 bajtów

->n{n+(1..n).sum{n-=(z=(n**0.5).to_i)*z;z*4}}

Wypróbuj online!

PHP , 67 bajtów

<?for($n=$argv[1];$w=(int)sqrt($n);$n-=$w**2)$a+=$w**2+$w*4;echo$a;

Aby uruchomić:

php -n <filename> <n>

Przykład:

php -n roman_army_shields.php 35

Lub wypróbuj online!

---

Za pomocą -Ropcji ta wersja ma 60 bajtów :

for(;$w=(int)sqrt($argn);$argn-=$w**2)$a+=$w**2+$w*4;echo$a;

Przykład:

echo 35 | php -nR "for(;$w=(int)sqrt($argn);$argn-=$w**2)$a+=$w**2+$w*4;echo$a;"

(w systemie Linux, należy wymienić "z ')

---

Uwaga: Korzystam z doskonałej formuły odpowiedzi Arnaulda , nie byłem w stanie znaleźć niczego krótszego.

Pyth , 19 bajtów

Funkcja rekurencyjna, którą należy wywołać za pomocą y(patrz link).

L&b+*Ks@b2+4Ky-b^K2

Wypróbuj tutaj!

Pyth , 21 bajtów

Historia zmian jest dość zabawna, ale koniecznie odwiedź ją, jeśli chcesz znacznie szybszej wersji :)

sm*d+4deeDsI#I#@RL2./

Wypróbuj tutaj!

Wyjaśnienie

sm*d+4deeDsI#I#@RL2./ Pełny program, nazwijmy wejście Q.
                   ./ Partycje całkowite Q. Daje wszystkie kombinacje dodatnie
                          liczby całkowite, które sumują się do Q.
               @ RL2 Weź pierwiastek kwadratowy ze wszystkich liczb całkowitych każdej partycji.
             I # Zachowaj tylko te partycje, które są niezmienne w:
          sI # Odrzucanie wszystkich liczb całkowitych. Zasadniczo zachowuje to tylko
                          partycje, które są w pełni utworzone z doskonałych kwadratów, ale
                          zamiast samych kwadratów, mamy ich korzenie.
       eeD Uzyskaj partycję (powiedzmy P) z najwyższym maksimum.
 m Dla każdego dw P ...
  * d + 4d ... Wydajność d * (d + 4) = d ^ 2 + 4d, wzór stosowany we wszystkich odpowiedziach.
s Sumuj wyniki tego odwzorowania i pośrednio uzyskaj wynik.

Swift 4 , 111 99 84 78 bajtów

func f(_ x:Int)->Int{var y=x;while y*y>x{y-=1};return x>0 ?(y+4)*y+f(x-y*y):0}

Wypróbuj online!

To uczucie przy ręcznym wdrażaniu pierwiastka kwadratowego z liczby całkowitej jest znacznie krótsze niż wbudowane ...

Nieoznakowany i wyjaśniony

// Define a function f that takes an integer, x, and returns another integer
// "_" is used here to make the parameter anonymous (f(x:...) -> f(...))
func f(_ x: Int) -> Int {

    // Assign a variable y to the value of x

    var y = x

    // While y squared is higher than x, decrement y.

    while y * y > x {
        y -= 1
    }

    // If x > 0, return (y + 4) * y + f(x - y * y), else 0.

    return x > 0 ? (y + 4) * y + f(x - y * y) : 0
}