Escudos del ejército romano

26

Publicación de sandbox (eliminada)

Las antiguas formaciones del ejército romano son muy famosas en todo el mundo. En estas formaciones, los legionarios romanos se agruparon en una forma geométrica (generalmente un rectángulo) protegiendo los flancos y la parte superior utilizando sus escudos. Los legionarios en posiciones interiores cubrían la parte superior colocando su escudo sobre sus cabezas, los legionarios en los flancos llevaban 2 o más escudos: uno para proteger la parte superior y uno o más escudos para proteger los flancos (si alguien estaba en la esquina tenía 3 escudos, si alguien estaba solo en una formación tenía 5 escudos Sí, sé que es imposible que un humano lleve 5 escudos, pero de alguna manera lo hicieron ). Usando esta formación, todos los legionarios romanos se protegieron y fueron el oponente más duro en ese momento.

La historia cuenta que hubo un general romano que declaró que la mejor forma de formación era el cuadrado (el mismo número de legionarios en filas y columnas). El problema era averiguar cuántas formaciones (y el tamaño) debía dividir su ejército para:

  • No dejó ningún legionario fuera de una formación (aunque admitió formación de legionario único)
  • Reduce la cantidad de escudos necesarios

El general, después de hacer algunos cálculos y matemáticas, descubrió que la mejor manera de lograr estas 2 condiciones es comenzar con el cuadrado más grande posible y luego repetir hasta que no quede ningún legionario .


Ejemplo:

Si 35 legionarios en su ejército, la formación consistía en

  • Un cuadrado de legionarios de 5x5 (este es el cuadrado más grande posible).

Con los legionarios restantes (10)

  • Un cuadrado de 3x3

Con los legionarios restantes (1)

  • Un cuadrado de 1x1.

Al final se verá más o menos así:

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

Los legionarios en posiciones interiores cubrían la parte superior colocando su escudo sobre sus cabezas . Solo necesitaban 1 escudo.

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

Los legionarios en los flancos llevaban 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 *               

Si alguien estaba en la esquina, tenía 3 escudos.

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               

Si alguien estaba solo en una formación, tenía 5 escudos.

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               

Esta formación requirió un total de 71 escudos.


Reto

  • Calcule la cantidad de escudos necesarios para una cantidad X de legionarios

Entrada

  • Cantidad de legionarios en el ejército.

Salida

  • Cantidad de escudos necesarios.

Casos de prueba

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

Luis felipe De jesus Munoz
fuente
11
Bueno, el resultado de Google para "llevar 5 escudos" es Amazon.com : Best-selling Nipple Shield Carrying Case, Perfect...así que supongo que nunca lo sabré realmente. ¿Realmente llevaban 5 escudos, o era para que la pregunta funcionara: P?
Urna de pulpo mágico el
1
@MagicOctopusUrn Estoy bastante seguro de que sabes la respuesta xD No creo que alguien tenga las agallas para salir en una pelea con 5 escudos
Luis felipe De jesus Munoz
44
No creo que las matemáticas y los cálculos del general sean correctos para concluir que tomar repetidamente el cuadrado más grande posible minimiza los escudos. Por ejemplo, 32 legionarios pueden dividirse en dos casillas de 4 * 4 para 64 escudos totales, en lugar de casillas de 5 * 5 + 2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 para 72 escudos totales.
xnor
66
@xnor Quizás en el caso general el general no estaba bien, pero el general es el general (aunque no deberíamos generalizar).
pajonk
2
@AJFaraday Astérix y los tejones mercenarios ?
Chris H

Respuestas:

14

Python 2 , 60 50 48 bytes

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

Pruébalo en línea!

¡Nuevo en el código de golf, pero dando mi mejor swing!

Método:

Suma n^2 + 4ndónde nestá cada uno de los números cuadrados más grandes que suman a la entrada.

Editar 1

¡Reducido a 50 bytes gracias a @Jonathan Frech!

Editar 2

Se cambió int(s**.5)a s**.5//1para guardar 2 bytes gracias a @ovs

Easton Bornemeier
fuente
8
Bienvenido a PPCG!
Luis felipe De jesus Munoz
2
Creo que n*nes más corto que n**2ahorrarte dos bytes; más que eso no puedo decir ya que no escribo python ...
Giuseppe
2
50 bytes .
Jonathan Frech
2
int(s**.5)se puede acortar a s**.5//1.
ovs
2
@mypetlion lo hace. //Esta división de piso en Python 2 y 3. se 3**.5//1evalúa 1.0en ambas versiones.
ovs
11

R , 51 50 bytes

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

Pruébalo en línea!

Un cuadrado de longitud lateral debe tener exactamente escudos. Reducimos por el cuadrado más grande menor o igual que hasta que sea ​​cero, acumulando el número de escudos a medida que avanzamos.yy2+4yxx

Prueba:

Dado un cuadrado perfecto de longitud lateral , necesitamos precisamente 1 escudo para cada miembro del cuadrado. A continuación, para cada miembro en el borde, necesitamos un escudo adicional. Hay miembros que no están en los bordes, por lo que hay miembros en los bordes. Finalmente, para cada esquina, necesitamos un escudo adicional. Además del caso donde , podemos sumar 4. Esto se simplifica a que afortunadamente también produce el valor correcto de cuando , lo que nos permite usarlo para todo .y(y2)2y2(y2)2y=1y2+4y5y=1y

Giuseppe
fuente
Puede simplificar mucho la explicación: cada cuadrado del techo debe cubrirse: , y cada cuadrado lateral debe cubrirse . Ahora es obvio que también funciona en el caso de un solo soldado. y24y
Todd Sewell el
1
@ToddSewell seguro, esa es la explicación de Arnauld , y es mucho más elegante, pero esta es la forma en que lo abordé , ¡así que me apego a ello! Afortunadamente, esta no es una pregunta de prueba de golf.
Giuseppe
10

JavaScript (ES7), 34 bytes

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

Pruébalo en línea!

¿Cómo?

w=nsw

sw=w2+4w

w=3

(323212323)=(s3=21)(111111111)+(3²=9)(111000000)+(001001001)+(000000111)+(100100100)(4×3=12)

La fórmula es válida para , ya que .s 1 = 5w=1s1=5

Arnauld
fuente
4

Julia 0.6 , 36 bytes

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

Pruébalo en línea!

Utiliza el mismo método que la respuesta R de @ Giuseppe, aunque mi método para llegar allí implicaba un pensamiento menos significativo y una inspección visual más justa: el cuadrado interno de 1s tiene dimensiones por , entonces eso tiene escudos. Alrededor de eso, hay 4 muros de soldados cada uno, cada uno con 2 escudos, por lo que agrega escudos. Finalmente, hay cuatro 3 en las cuatro esquinas, por lo que agrega 12 escudos.n2+4n(n2)(n2)(n2)2n24(n2)2

(n2)2+4(n2)2+43=n2+44n+8n16+12=n2+4n

Sin golf:

!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

(Esto también se puede hacer en 35 bytes con n>0?(s=isqrt(n))*s+4s+f(n-s*s):0, pero escribí esto para Julia 0.7 quería evitar las nuevas advertencias de desaprobación (los espacios que requieren son ?y :).

sundar - Restablecer a Monica
fuente
Otra explicación demasiado complicada para el recuento de escudos, vea mi comentario sobre la respuesta de @ Giuseppe.
Todd Sewell el
2
@ToddSewell Sí, área + perímetro es una forma más elegante de verlo. Sin embargo, no lo hice de esa manera, y de manera similar a Giuseppe, mi intención es describir mi enfoque en lugar de dar la mejor prueba de la fórmula.
Sundar - Restablecer Monica
3

Brachylog , 26 bytes

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

Pruébalo en línea!

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
sundar - Restablecer a Monica
fuente
2

Retina 0.8.2 , 28 bytes

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

Pruébalo en línea! El enlace incluye casos de prueba. Explicación:

.+
$*

Convierte a decimal.

(\G1|11\1)+

Empareja números impares. El primer paso por el grupo \1aún no existe, por lo que solo \G1puede coincidir, que coincide con 1. Las coincidencias posteriores no pueden coincidir, \G1ya que \Gsolo coinciden al comienzo del partido, por lo que tenemos que hacer coincidir el 11\1que es 2 más que El partido anterior. Emparejamos tantos números impares como podamos y, por lo tanto, la coincidencia total es un número cuadrado, mientras que la última captura es uno menos del doble de su lado.

$&11$1$1

$&n2$12n1n2+4n=n2+2+2(2n1)

.

Suma y convierte a decimal.

Neil
fuente
2

05AB1E , 17 bytes

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

Pruébelo en línea o verifique todos los casos de prueba .

Solución temporal porque ΔDtïÐns4*+Šn-}O( 15 bytes ) no parece funcionar ... Pruébelo en línea en modo de depuración para ver a qué me refiero. Esperaría que fuera de [45,'35',25]a [45,10]después de la -siguiente iteración de Δ, pero aparentemente borra la pila excepto por el último valor y se convierte en[10] , dando como resultado 0 al final ... No estoy seguro de si este es el comportamiento previsto o un error ... (EDITAR: está destinado, ver abajo).

Explicación:

w2+4ww

[        }     # 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

EDITAR: Aparentemente, el comportamiento que describí anteriormente Δestá destinado. Aquí hay dos alternativas de 17 bytes proporcionadas por @ Mr.Xcoder que se usan Δcolocando valores en global_array (con ^) y recuperándolos nuevamente después (con ¯):

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

Pruébelo en línea o verifique todos los casos de prueba .

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

Pruébelo en línea o verifique todos los casos de prueba .

Kevin Cruijssen
fuente
2

dc , 25 bytes

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

Pruébalo en línea!

Calcula los escudos como sum(n^2)(el número original) más 4*sum(n)empujando una copia de cada longitud del lado cuadrado en el registro de la pila a amedida que avanza, luego agrega todos los valores del registro a amedida que la recursión se "desenrolla".

Sophia Lechner
fuente
1

PHP , 67 bytes

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

Para ejecutarlo:

php -n <filename> <n>

Ejemplo:

php -n roman_army_shields.php 35

O Pruébelo en línea!


Usando la -Ropción, esta versión es de 60 bytes :

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

Ejemplo:

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

(en Linux, reemplace "con ')


Nota: Esto está usando la excelente fórmula de respuesta de Arnauld , no pude encontrar nada más corto que eso.

Noche2
fuente
1

Pyth , 19 bytes

Una función recursiva, que debe llamarse usando y(ver el enlace).

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

Pruébalo aquí!

Pyth , 21 bytes

El historial de revisiones es bastante divertido, pero asegúrese de visitarlo si desea una versión mucho más rápida :)

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

Pruébalo aquí!

Explicación

sm*d+4deeDsI#I#@RL2./ Programa completo, llamemos a la entrada Q.
                   ./ Particiones enteras de Q. Produce todas las combinaciones de positivo
                          enteros que se suman a Q.
               @ RL2 Saca la raíz cuadrada de todos los enteros de cada partición.
             I # Guarde solo las particiones que son invariables bajo:
          sI # Descartando todos los no enteros. Esto básicamente solo mantiene el
                          particiones que se forman completamente de cuadrados perfectos, pero
                          en lugar de tener los cuadrados en sí, tenemos sus raíces.
       eeD Obtenga la partición (digamos P) con el máximo más alto.
 m Para cada d en P ...
  * d + 4d ... Rendimiento d * (d + 4) = d ^ 2 + 4d, la fórmula utilizada en todas las respuestas.
s Suma los resultados de esta asignación y la salida implícita.
Sr. Xcoder
fuente
1

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}

Pruébalo en línea!

Esa sensación al implementar manualmente la raíz cuadrada entera es mucho más corta que la incorporada ...

No golfista y explicado

// 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
}
Sr. Xcoder
fuente