^{Sandbox-Post (gelöscht)}

Die alten römischen Heeresformationen sind auf der ganzen Welt sehr berühmt. In diesen Formationen gruppieren sich römische Legionäre in einer geometrischen Form (normalerweise ein Rechteck), die die Flanken und den oberen Teil mit ihren Schilden schützen. Die Legionäre in den inneren Stellungen bedeckten den oberen Teil mit ihrem Schild über dem Kopf, die Legionäre an den Flanken trugen 2 oder mehr Schilde: einen zum Schutz des oberen Teils und einen oder mehrere Schilde zum Schutz der Flanken (falls sich jemand in der Ecke befand) er hatte 3 Schilde, wenn jemand alleine in einer Formation war, hatte er 5 Schilde ^{Ja, ich weiß, es ist für einen Menschen unmöglich, 5 Schilde zu tragen, aber irgendwie haben sie es geschafft} . Mit dieser Formation schützten sich alle römischen Legionäre und waren zu dieser Zeit der härteste Gegner.

Aus der Geschichte geht hervor, dass es einen römischen General gab, der erklärte, die beste Form der Formation sei das Quadrat (die gleiche Anzahl von Legionären in Reihen und Spalten). Das Problem bestand darin, herauszufinden, wie viele Formationen (und wie groß) er sein Heer aufteilen sollte, um:

• Lasse keinen Legionär aus einer Formation (obwohl er eine einzelne Legionärsformation zugelassen hat)
• Reduzieren Sie die Anzahl der erforderlichen Schilde

Nach einigen Berechnungen stellte der General fest, dass der beste Weg, um diese beiden Bedingungen zu erfüllen, darin besteht, mit dem größtmöglichen Quadrat zu beginnen und es dann zu wiederholen, bis keine Legionäre mehr übrig sind .

Beispiel:

Befanden sich 35 Legionäre in seiner Armee, bestand die Formation aus

• Ein 5x5 Legionärsquadrat (Dies ist das größte mögliche Quadrat).

Mit den restlichen Legionären (10)

• Ein 3x3 Quadrat

Mit den restlichen Legionären (1)

• Ein 1x1 Quadrat.

Am Ende wird es ungefähr so ​​aussehen:

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

Die Legionäre in den inneren Stellungen deckten den überlegenen Teil ab und legten ihren Schild über die Köpfe . Sie brauchten nur 1 Schild.

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

Die Legionäre an den Flanken trugen 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 *               

Wenn jemand in der Ecke war, hatte er 3 Schilde

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               

Wenn jemand alleine in einer Formation war, hatte er 5 Schilde

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               

Diese Formation erforderte insgesamt 71 Schilde.

Herausforderung

• Berechnen Sie die Anzahl der Schilde, die für eine X-Anzahl von Legionären benötigt werden

Eingang

• Anzahl der Legionäre in der Armee

Ausgabe

• Anzahl der benötigten Schilde.

Testfälle

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

• Standard Code-Golfregeln gelten

Python 2 , 60 50 48 Bytes

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

Probieren Sie es online!

Neu im Code-Golf, aber mein bester Schlag!

Methode:

Summe, n^2 + 4nwobei njedes der größten Quadrate die Summe für die Eingabe ist.

Bearbeiten 1

Reduziert auf 50 Bytes dank @Jonathan Frech!

Bearbeiten 2

Switched int(s**.5)zu s**.5//12 Byte dank @ovs zu speichern

R , 51 50 Bytes

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

Probieren Sie es online!

Ein Quadrat mit der Seitenlänge muss genau Schilde haben. Wir reduzieren um das größte Quadrat, das kleiner oder gleich bis Null ist, und akkumulieren dabei die Anzahl der Schilde.$y$$y^2+4y$$x$$x$

Beweis:

Bei einem perfekten Quadrat mit der Seitenlänge benötigen wir genau 1 Schild für jedes Mitglied des Quadrats. Als nächstes benötigen wir für jedes Mitglied am Rand einen zusätzlichen Schild. Es gibt Glieder, die nicht an den Rändern sind, also gibt es Glieder an den Rändern. Schließlich benötigen wir für jede Ecke einen zusätzlichen Schild. Abgesehen von dem Fall, in dem , können wir also 4 addieren. Dies vereinfacht sich zu was zum Glück auch den korrekten Wert ergibt, wenn , so dass wir ihn für alle .$y$$(y-2)^2$$y^2-(y-2)^2$$y=1$$y^2+4y$$5$$y=1$$y$

JavaScript (ES7), 34 Byte

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

Probieren Sie es online!

Wie?

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

$w=3$

Die Formel gilt für als .$w=1$$s_1=5$

Gelee , 13 Bytes

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

Probieren Sie es online!

-1 Danke an Jonathan Allan .

Julia 0,6 , 36 Bytes

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

Probieren Sie es online!

Verwendet die gleiche Methode wie @ Giuseppes R-Antwort, obwohl meine Methode, dorthin zu gelangen, weniger aussagekräftiges Denken und eine gerechtere visuelle Betrachtung beinhaltete: Das innere Quadrat von 1s hat Dimensionen mal . das hat also Schilde. Um das herum gibt es 4 Mauern mit jeweils Soldaten mit jeweils 2 Schilden - so dass Schilden hinzukommen. Schließlich gibt es vier 3s in den vier Ecken, so dass 12 Schilde hinzugefügt werden.$n^2 + 4n$$(n - 2)$$(n - 2)$$(n - 2)^2$$n - 2$$4*(n - 2)*2$

Ungolfed:

!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

(Das kann man auch in 35 Bytes mit machen n>0?(s=isqrt(n))*s+4s+f(n-s*s):0, aber ich habe das für Julia 0.7 geschrieben, um die neuen Verwerfungswarnungen zu vermeiden (Leerzeichen sind erforderlich ?und :).)

Stax , 15 Bytes

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

Führen Sie es aus und debuggen Sie es

Brachylog , 26 Bytes

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

Probieren Sie es 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 Bytes

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

Probieren Sie es online! Link enthält Testfälle. Erläuterung:

.+
$*

In Dezimalzahl konvertieren.

(\G1|11\1)+

Ordne ungeraden Zahlen zu. Der erste Durchlauf durch die Gruppe, \1gibt es noch nicht, so dass nur \G1mithalten kann, die 1. Nachträgliche Spiele Spiele nicht mithalten können , \G1da \Gnur Matches zu Beginn des Spiels, so stattdessen müssen wir das Spiel , 11\1das 2 ist mehr als das vorherige Spiel. Wir passen so viele ungerade Zahlen an, wie wir können, und die Gesamtübereinstimmung ist daher eine quadratische Zahl, während die letzte Erfassung eins weniger als das Doppelte ihrer Seite ist.

$&11$1$1

Fügen Sie die Seitenschilde zu jedem Match hinzu. $&ist und ist während wir brauchen .$n^2$$1$2n-1$$n^2+4n=n^2+2+2(2n-1)$

.

Summieren und in Dezimalzahl umwandeln.

05AB1E , 17 Bytes

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

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Problemumgehung, da ΔDtïÐns4*+Šn-}O( 15 Byte ) nicht zu funktionieren scheint. Versuchen Sie es online im Debug-Modus, um zu sehen, was ich meine. Ich würde erwarten , dass es von gehen , [45,'35',25]um [45,10]nach der -und im nächsten Iteration Δ, aber anscheinend löscht er den Stapel mit Ausnahme des letzten Wert und wird [10]in 0 am Ende resultierenden .. Nicht sicher , ob dieses Verhalten oder einen Bug soll .. (EDIT: Es ist vorgesehen, siehe unten.)

Erläuterung:

Verwendet auch wobei wie die meisten anderen Antworten die Breite in einer Schleife ist.$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

EDIT: Anscheinend ist das oben beschriebene Verhalten Δbeabsichtigt. Hier zwei 17-Byte-Alternativen von @ Mr.Xcoder , die verwendet Δwerden, indem Werte in das global_array eingegeben (mit ^) und anschließend erneut abgerufen werden (mit ¯):

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

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

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

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Gleichstrom , 25 Bytes

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

Probieren Sie es online!

Berechnet die Schilde als sum(n^2)(die ursprüngliche Zahl) plus, 4*sum(n)indem Sie eine Kopie jeder quadratischen Seitenlänge nacheinander in das Stapelregister schieben aund dann alle Werte aus dem Register addieren, awährend die Rekursion "abrollt".

Schale , 17 Bytes

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

Probieren Sie es online!

Alternative

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

Probieren Sie es online!

APL (Dyalog Unicode) , 31 30 Bytes

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

Probieren Sie es online!

-1 Byte dank @jslip

Ruby , 45 Bytes

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

Probieren Sie es online!

PHP , 67 Bytes

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

Um es auszuführen:

php -n <filename> <n>

Beispiel:

php -n roman_army_shields.php 35

Oder versuchen Sie es online!

Mit der -ROption ist diese Version 60 Bytes :

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

Beispiel:

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

(unter Linux ersetzen "durch ')

Hinweis: Dies ist die Antwortformel von Arnauld. Ich konnte nichts Kürzeres finden.

Pyth , 19 Bytes

Eine rekursive Funktion, die mit aufgerufen werden soll y(siehe Link).

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

Probieren Sie es hier aus!

Pyth , 21 Bytes

Das Revisionsprotokoll ist ziemlich lustig, aber besuchen Sie es unbedingt, wenn Sie eine viel schnellere Version wünschen :)

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

Probieren Sie es hier aus!

Erläuterung

sm*d+4deeDsI#I#@RL2./ Vollständiges Programm, rufen wir den Eingang Q auf.
                   ./ Integer-Partitionen von Q. Ergibt alle positiven Kombinationen
                          ganze Zahlen, die sich zu Q addieren.
               @ RL2 Nimm die Quadratwurzel aller ganzen Zahlen jeder Partition.
             I # Behalte nur die Partitionen, die unveränderlich sind unter:
          sI # Alle Nicht-Ganzzahlen verwerfen. Dies hält im Grunde nur die
                          Partitionen, die voll von perfekten Quadraten gebildet werden, aber
                          Anstatt die Quadrate selbst zu haben, haben wir ihre Wurzeln.
       eeD Holen Sie sich die Partition (sagen wir P) mit dem höchsten Maximum.
 m Für jedes d in P ...
  * d + 4d ... Ausbeute d * (d + 4) = d ^ 2 + 4d, die in allen Antworten verwendete Formel.
s Summieren Sie die Ergebnisse dieser Zuordnung und geben Sie sie implizit aus.

Swift 4 , 111 99 84 78 Bytes

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}

Probieren Sie es online!

Dieses Gefühl bei der manuellen Implementierung von Integer-Quadratwurzeln ist weitaus kürzer als die ...

Ungolfed und erklärt

// 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
}