Всё могут короли (Время: 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.