^{Сообщение песочницы (удалено)}

Старые формирования римской армии очень известны во всем мире. В этих формированиях римские легионеры группировались в геометрическую форму (обычно прямоугольник), защищая фланги и превосходящую его часть с помощью своих щитов. Легионеры во внутренних помещениях прикрывали верхнюю часть, размещая свой щит над головами, легионеры по бокам несли 2 или более щитов: один для защиты верхней части и один или несколько щитов для защиты флангов (если кто-то находился в углу у него было 3 щита, если кто-то был один в строю, у него было 5 щитов. ^{Да, я знаю, что человек не может носить 5 щитов, но каким-то образом они это сделали} ). Используя это формирование, все римские легионеры защитились и были самым сильным противником в то время.

История рассказывает, что был римский генерал, который утверждал, что лучшей формой формирования был квадрат (такое же количество легионеров в строках и столбцах). Проблема заключалась в том, чтобы выяснить, сколько формирований (и размер) он должен разделить свою армию, чтобы:

• Не оставляйте ни одного легионера за пределами формирования (хотя он допускал единственное легионерное формирование)
• Уменьшите количество необходимых щитов

Генерал, после некоторой математики и вычислений, он понял, что лучший способ выполнить эти 2 условия - начать с максимально возможного квадрата, а затем повторить, пока не останется легионеров .

---

Пример:

Если 35 легионеров в его армии, формирование состояло в

• Площадь легионеров 5х5 (это самая большая площадь из возможных).

С остальными легионерами (10)

• Квадрат 3х3

С остальными легионерами (1)

• Квадрат 1х1.

В конце это будет выглядеть примерно так:

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

Легионеры во внутренних помещениях покрывали верхнюю часть, размещая свой щит над головами . Им нужен был только 1 щит.

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

Легионеры на флангах несут 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 *               

Если кто-то был в углу, у него было 3 щита

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               

Если кто-то был один в строю, у него было 5 щитов

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               

Для этого формирования потребовалось в общей сложности 71 щит.

---

Вызов

• Рассчитайте количество щитов, необходимых для X количества легионеров

вход

• Количество легионеров в армии

Выход

• Необходимое количество щитов.

Тестовые случаи

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

---

• Применяются стандартные правила игры в гольф

Python 2 , 60 50 48 байтов

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

Попробуйте онлайн!

Новичок в коде гольф, но я делаю это как можно лучше!

Метод:

Сумма n^2 + 4nгде nкаждое из наибольших квадратных чисел, которые суммируют с вводом.

Редактировать 1

Благодаря @Jonathan Frech уменьшено до 50 байт!

Редактировать 2

Переключился int(s**.5)на s**.5//1сохранение 2 байта благодаря @ovs

R , 51 50 байт

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

Попробуйте онлайн!

$y$$y^2+4y$$x$$x$

Доказательство:

$y$$(y-2)^2$$y^2-(y-2)^2$$y=1$$y^2+4y$$5$$y=1$$y$

JavaScript (ES7), 34 байта

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

Попробуйте онлайн!

Как?

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

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

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

Формула верна для , так как .$w=1$$s_1=5$

Желе , 13 байт

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

Попробуйте онлайн!

-1 спасибо Джонатану Аллану .

Юлия 0,6 , 36 байт

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

Попробуйте онлайн!

Используется тот же метод что и в ответе @ Giuseppe's R, хотя мой метод для этого заключался в менее значительном мышлении и больше просто визуальном осмотре: внутренний квадрат 1s имеет размеры по , так что имеет щита. Вокруг этого есть 4 стены по солдата в каждой, каждая с 2 щитами - так что добавляется щита. Наконец, в четырех углах есть четыре тройки, так что добавляется 12 щитов.$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$$

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

(Это также может быть сделано в 35 байтах с n>0?(s=isqrt(n))*s+4s+f(n-s*s):0, но я написал это для Julia 0.7, хотел избежать новых предупреждений об устаревании (требующие пробелы ?и :).)

Stax , 15 байт

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

Запустите и отладьте его

Брахилог , 26 байт

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

Попробуйте онлайн!

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

Сетчатка 0.8.2 , 28 байт

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

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Объяснение:

.+
$*

Преобразовать в десятичную.

(\G1|11\1)+

Совпадение нечетных чисел. Первый проход через группу \1еще не существует, поэтому \G1может совпадать только тот , который соответствует 1. Последующие совпадения не могут совпадать, \G1поскольку совпадают \Gтолько совпадения в начале матча, поэтому вместо этого мы должны сопоставить значение, 11\1которое на 2 больше, чем предыдущий матч. Мы сопоставляем столько нечетных чисел, сколько можем, и поэтому общее совпадение представляет собой квадратное число, в то время как последний снимок равен одному меньше, чем его сторона.

$&11$1$1

$&$n^2$$1$2n-1$$n^2+4n=n^2+2+2(2n-1)$

.

Суммируйте и преобразуйте в десятичную.

05AB1E , 17 байт

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

Попробуйте онлайн или проверьте все контрольные примеры .

Обходной путь, потому что ΔDtïÐns4*+Šn-}O( 15 байт ), похоже, не работает .. Попробуйте онлайн в режиме отладки, чтобы понять, что я имею в виду. Я ожидал бы , чтобы перейти от [45,'35',25]к [45,10]после -и следующей итерации Δ, но , видимо , она очищает стек для последнего значения , за исключением , и становится [10], в результате 0 в самом конце .. Не уверен , если это предназначено поведение или ошибка .. (РЕДАКТИРОВАТЬ: Это предназначено, см. Внизу.)

Объяснение:

$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

---

РЕДАКТИРОВАТЬ: Очевидно, поведение, для которого я описал выше, Δпредназначено. Вот две 17- байтовые альтернативы, предоставленные @ Mr.Xcoder, которые используют Δ, помещая значения в global_array (с ^) и получая их снова после (с ¯):

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

Попробуйте онлайн или проверьте все контрольные примеры .

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

Попробуйте онлайн или проверьте все контрольные примеры .

постоянный ток , 25 байтов

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

Попробуйте онлайн!

Вычисляет щиты как sum(n^2)(исходное число) плюс 4*sum(n), помещая копию каждой длины стороны квадрата в регистр стека, aа затем добавляя все значения из регистра, aпоскольку рекурсия «разворачивается».

Шелуха , 17 байт

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

Попробуйте онлайн!

альтернатива

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

Попробуйте онлайн!

APL (Dyalog Unicode) , 31 30 байт

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

Попробуйте онлайн!

-1 байт благодаря @jslip

Рубин , 45 байт

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

Попробуйте онлайн!

PHP , 67 байт

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

Чтобы запустить это:

php -n <filename> <n>

Пример:

php -n roman_army_shields.php 35

Или попробуйте онлайн!

---

Используя -Rопцию, эта версия составляет 60 байт :

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

Пример:

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

(в Linux заменить "на ')

---

Примечание: здесь используется замечательная формула ответа Арно , я не смог найти ничего короче этого.

Pyth , 19 байт

Рекурсивная функция, которую следует вызывать с помощью y(см. Ссылку).

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

Попробуй это здесь!

Pyth , 21 байт

История изменений довольно забавная, но обязательно посетите ее, если вы хотите намного более быструю версию :)

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

Попробуй это здесь!

объяснение

sm*d+4deeDsI#I#@RL2./ Полная программа, давайте назовем вход Q.
                   ./ Целочисленные разбиения Q. Получает все комбинации положительных
                          целые числа, которые складываются в Q.
               @ RL2 Возьмите квадратный корень из всех целых чисел каждого раздела.
             Я # Сохраняю только те разделы, которые инвариантны относительно:
          sI # Отбрасывать все нецелые числа. Это в основном только держит
                          перегородки, которые сформированы полностью из идеальных квадратов, но
                          вместо того, чтобы иметь сами квадраты, у нас есть их корни.
       eeD Получить раздел (скажем, P) с наибольшим максимумом.
 м за каждый д в п ...
  * d + 4d ... Выход d * (d + 4) = d ^ 2 + 4d, формула, используемая во всех ответах.
s Суммируйте результаты этого отображения и неявно выводите.

Swift 4 , 111 99 84 78 байт

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}

Попробуйте онлайн!

Это чувство при реализации целочисленного квадратного корня вручную намного короче, чем встроенный ...

Неуправляемый и объясненный

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