Всё могут короли (Время: 1 сек. Память: 32 Мб Сложность: 7%) Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По размеру доски определите…

Задача: разместить королей на квадратной доске n x n так, чтобы ни один не атаковал другого, и при этом не осталось свободного места для добавления ещё одного короля. Нужно дать решение на C++.

Идея решения

• Два короля не могут находиться на соседних клетках, даже по диагонали. Значит, если мы расставим королей только на клетках с обеими координатами нечётными: (1,1), (1,3), (1,5), ..., (3,1), (3,3), ...
• На доске n x n таких клеток с нечётными координатами по одной оси ровно ceil(n/2) штук. Поэтому всего получится ceil(n/2) · ceil(n/2) королей.
• Этот набор королей не конфликтует между собой, потому что расстояния между любыми двумя такими клетками по любой оси минимум 2.
• Он же максимален: скажем, расположение на нечётных координатах уже максимизирует количество королей, и любой пустой квадрат обязательно будет находиться рядом с одной из таких королевских клеток (например, если клетка (i,j) не в наборе, то её ближайшая "чётная пара" клетка (i-1, j-1) или (i, j-1) и т.д. будет атакована).

Итого формула

• Максимальное количество королей = ceil(n/2)².
• В целочисленной арифметике: t = (n + 1) / 2, ответ = t * t.

Сложность: O(1) по времени, O(1) по памяти.

Пример кода на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    if (!(cin >> n)) return 0;

    long long t = (n + 1) / 2; // ceil(n/2)
    cout << t * t << "\n";

    return 0;
}

Примечания

• Ввод: одно число n (размер доски n x n).
• Поддерживаются большие n за счет использования long long.
• Если нужно обработать несколько тестов за один запуск, можно поместить чтение в цикл while (cin >> n) и выводить ответ для каждого n.