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

Рассмотрим задачу по размещению королей на шахматной доске размером \( n \times n \), так чтобы они не угрожали друг другу. Король может атаковать все клетки вокруг себя, включая диагонали, что означает, что на соседние клетки по вертикали, горизонтали и диагонали нельзя ставить других королей.

На шахматной доске существует способ размещения королей с максимальной плотностью. Одним из эффективных методов является использование шахматного паттерна, который позволяет минимизировать количество свободных клеток вокруг размещенных королей.

Алгоритм:

1. Обычно максимальное количество королей, которое можно разместить, без угрозы друг другу, на доске размером \( n \times n \) можно определить, если разбить доску на 2×2 квадраты.
2. В каждом таком квадрате можно разместить одного короля, что позволит установить его так, чтобы ни один из других королей не угрожал ему.
3. Таким образом, на доске размером \( n \times n \) общее количество 2x2 квадратов можно вычислить как \( \left\lfloor \frac{n + 1}{2} \right\rfloor \times \left\lfloor \frac{n + 1}{2} \right\rfloor \), что даст нам максимальное количество королей.

Формула:

\[ \text{Количество королей} = \left\lceil \frac{n}{2} \right\rceil \times \left\lceil \frac{n}{2} \right\rceil \] где \( \left\lceil x \right\rceil \) – это функция округления до ближайшего большего целого.

Пример:

Для \( n = 3 \):

• \( \left\lceil \frac{3}{2} \right\rceil = 2 \),
• \( \left\lceil \frac{3}{2} \right\rceil = 2 \),
• Количество королей = \( 2 \times 2 = 4 \).

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

Вывод:

Если вы хотите узнать, сколько королей можно разместить на конкретной доске, просто подставьте значение \( n \) в указанную формулу, и вы получите ответ.