26
3
The old roman army formations are very famous around the world. In these formations roman legionaries grouped in a geometric shape (usually a rectangle) protecting the flanks and the superior part of it using their shields. The legionaries at interior positions covered the superior part placing their shield above their heads, the legionaries at the flanks carried 2 or more shields: one for protecting the superior part, and one or more shields for protecting the flanks (if someone was in the corner he had 3 shields, if someone was alone in a formation he had 5 shields Yes, I know it is impossible for a human to carry 5 shields, but somehow they did it). Using this formation all roman legionaries protected themselves and were the hardest opponent at the time.
The history tells there was a roman general who stated that the best formation shape was the square (same number of legionaries in rows and columns). The problem was figuring out how many formations (and the size) he should split his army in order to:
- Do not left any legionary out of a formation (although he admitted single legionary formation)
- Reduce the amount of required shields
The general, after doing some math and calculations, he figured out that the best way to accomplish this 2 conditions is to start with the biggest square possible, and then repeat until no legionaries left.
Example:
If 35 legionaries in his army, the formation consisted in
- A 5x5 legionaries square (This is the biggest square possible).
With the remaining legionaries (10)
- A 3x3 square
With the remaining legionaries (1)
- A 1x1 square.
At the end it will look something like this:
5x5
* * * * * 3x3
* * * * * * * * 1x1
* * * * * * * * *
* * * * * * * *
* * * * *
The legionaries at interior positions covered the superior part placing their shield above their heads. They only needed 1 shield.
* * * * *
* 1 1 1 * * * *
* 1 1 1 * * 1 * *
* 1 1 1 * * * *
* * * * *
The legionaries at the flanks carried 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 *
If someone was in the corner he had 3 shields
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
If someone was alone in a formation he had 5 shields
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
This formation required a total of 71 shields.
Challenge
- Calculate the amount of shields that are needed for a X amount of legionaries
Input
- Amount of legionaries in the army
Output
- Amount of shields needed.
Test Cases
35 => 71
20 => 44
10 => 26
32 => 72
- Standard code-golf rules apply
How... How does one carry 5 shields? 2 in each hand, 2 in each foot and one in his mouth? – Magic Octopus Urn – 2018-08-02T20:23:48.243
@MagicOctopusUrn I can not sleep at nights only thinking about that xD – Luis felipe De jesus Munoz – 2018-08-02T20:24:43.637
11Well the google result for "carrying 5 shields" is
Amazon.com : Best-selling Nipple Shield Carrying Case, Perfect...
so I guess I'll never truly know. Did they actually carry 5 shields-- or was this to make the question work :P? – Magic Octopus Urn – 2018-08-02T20:25:40.527@MagicOctopusUrn They would likely never be on their own. – Okx – 2018-08-02T20:29:05.210
@Okx I assumed-- but my only knowledge about shield walls begins and ends with the movie 300 hah! – Magic Octopus Urn – 2018-08-02T20:32:02.443
1@MagicOctopusUrn Im pretty sure you know the answer xD I don't think someone has the guts to go out in a fight with 5 shields – Luis felipe De jesus Munoz – 2018-08-02T20:32:17.833
History has taught me not to underestimate the Romans hehe :). – Magic Octopus Urn – 2018-08-02T20:33:09.673
1
Not that it's really helpful, but A028347 gives the number of shields for a given square.
– Arnauld – 2018-08-02T21:29:40.953Not that historicity matters here, but your description of what is called a testudo formation is not quite right. The flanks and back of the formation were typically left unshielded, with only the front and top of the formation remaining shielded. Each soldier would have only carried one shield.
– Ethan Bierlein – 2018-08-02T22:39:31.7034I don't the general's math and calculations are right to conclude that repeatedly taking the largest square possible necessary minimizes shields. For example, 32 legionaries can split into two 44 squares for 64 total shields, rather than squares of 55 + 22 +11 + 11 + 11 for 72 total shields. – xnor – 2018-08-03T00:29:28.580
@xnor you are right, it is not the best way to minimize the amount of shields (it was discussed in the sandbox) but the general is the general. – Luis felipe De jesus Munoz – 2018-08-03T00:31:30.853
6@xnor Maybe in general case the general was't right, but the general is the general (although we shouldn't generalize). – pajonk – 2018-08-03T05:04:38.483
But... what about attacks from below? – AJFaraday – 2018-08-03T08:27:36.780
2@AJFaraday Asterix and the mercenary badgers? – Chris H – 2018-08-03T09:13:32.363