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

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

• \( (i-1, j-1) \)
• \( (i-1, j) \)
• \( (i-1, j+1) \)
• \( (i, j-1) \)
• \( (i, j+1) \)
• \( (i+1, j-1) \)
• \( (i+1, j) \)
• \( (i+1, j+1) \)

Таким образом, для размещения королей удобен шахматный подход с чередующимися клетками.

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

• Если \( n \) четное, то максимальное количество королей будет равно \( \frac{n^2}{2} \).
• Если \( n \) нечетное, то количество будет равно \( \frac{n^2 + 1}{2} \) (чуть больше половины).

Примерный код на Python:

def max_kings(n):
    if n % 2 == 0:
        return (n * n) // 2
    else:
        return (n * n + 1) // 2

n = int(input().strip())
print(max_kings(n))

Для данного кода:

• Функция max_kings принимает размер доски \( n \) и возвращает максимальное количество королей.
• Мы делим площадь доски на 2 и учитываем дополнительный король, если размер доски нечётный.

Таким образом, наибольшее количество королей, которое можно разместить на шахматной доске \( n \times n \) – это \( \lceil n^2 / 2 \rceil \).