Всё могут короли! Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). 👉По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно. Формат входных данных Единственная строка входного файла содержит одно натуральное число n (1 ≤ n ≤ 10%) - размер квадратной шахматной доски. Формат выходных данных Выведите одно натуральное число — ответ на вопрос задачи. 👉Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64-битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java. Система оценки 👉Решения, верно работающие при 1 ≤ n ≤ 100, получат не менее 30 баллов. 👉Решения, верно работающие при 1 ≤ n ≤ 10%, получат не менее 60 баллов

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

Наиболее эффективный способ расставить королей - это использовать шахматную доску в виде чередующихся клеток. Рассмотрим два случая в зависимости от четности размера доски \( n \):

1. Если \( n \) - четное число:

   • Например, для доски \( 2 \times 2 \) можно расставить королей в каждом углу:

     K .
     . K
     

   • Каждые два ряда могут вмещать 2 короля, следовательно: \[ \text{Общее количество королей} = \frac{n \times n}{2} \]

2. Если \( n \) - нечетное число:

   • В этом случае можно расставить королей более оптимально, но так, чтобы по-прежнему оставалось минимум клеток для добавления нового короля:

     K . K
     . K .
     K . K
     

   • В этом случае также можно использовать формулу: \[ \text{Общее количество королей} = \frac{(n + 1) \times (n + 1)}{2} \]

Таким образом, мы можем обобщить результат для любого \( n \):

• Если \( n \) четное: \[ \text{Королей} = \frac{n^2}{2} \]

• Если \( n \) нечетное: \[ \text{Королей} = \frac{(n^2 + 1)}{2} \]

Используя эти формулы, вы сможете получить максимальное количество королей для заданного размера доски \( n \). Не забудьте использовать 64-битный тип данных для больших значений \( n \).

Теперь вы можете реализовать этот алгоритм в вашем коде!