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

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

Таким образом, наиболее эффективным способом размещения королей является расстановка их в шахматном порядке: например, на клетках типа (0,0), (0,2), (1,1), (1,3) и так далее. Формально это можно выразить следующим образом:

1. Если размер доски четный (n % 2 == 0), максимальное количество королей будет равно (n * n) / 2.
2. Если размер доски нечетный (n % 2 == 1), максимальное количество королей будет равно (n * n + 1) / 2.

Таким образом, алгоритм такой:

• Подсчитать общее количество клеток на доске (n * n).
• Если n четное, то ответом будет (n * n) // 2.
• Если n нечетное, то ответом будет (n * n + 1) // 2.

Пример кода на Python, реализующего данное решение:

def max_king_positions(n):
    # Общее число клеток на доске
    total_cells = n * n
    
    # Для четного n
    if n % 2 == 0:
        return total_cells // 2
    else:
        # Для нечетного n
        return (total_cells + 1) // 2

# Читаем размер доски
n = int(input().strip())
# Получаем максимальное количество королей
result = max_king_positions(n)
# Выводим результат
print(result)

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