Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По размеру доски…

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

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

Рассмотрим различные случаи в зависимости от четности \( n \):

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

   • На доске будет \( n^2 \) клеток, и каждая цветная область будет содержать \( n^2 / 2 \) клеток. Это означает, что мы можем разместить королей на всех клетках одного цвета, что даст нам \( n^2 / 2 \) королей.

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

   • На доске будет \( n^2 \) клеток. Одна цветная область будет иметь \( (n^2 + 1) / 2 \) клеток, а другая \( (n^2 - 1) / 2 \) клеток. Мы можем разместить королей на клетках цвета, который имеет больше клеток, что вновь дает \( (n^2 + 1) / 2 \).

Таким образом, формула для максимального числа королей, которые можно расположить на доске \( n \times n \), будет:

\[ \text{число королей} = \left\lceil \frac{n^2}{2} \right\rceil \]

В программном коде это можно реализовать, например, так (в C++):

#include <iostream>

int main() {
    long long n;
    std::cin >> n;
    long long result = (n * n + 1) / 2; // Это даёт целочисленное деление и "округление вверх"
    std::cout << result << std::endl;
    return 0;
}

Теперь вы знаете, как вычислить максимальное количество королей на шахматной доске. Удачи в решении задач!