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

Чтобы определить максимальное количество королей, которые можно разместить на шахматной доске размером n × n, нужно учитывать, что короли не могут находиться на соседних клетках, включая диагонали.

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

При размещении королей на доске, можно использовать шахматный принцип, когда мы чередуем клетки. Например, можно размещать королей только на черных клетках или только на белых клетках. Если вы используете черные клетки, то для доски n × n количество королей будет равно количеству доступных черных клеток, которое в случае четного n будет n²/2, а в случае нечетного n будет (n² + 1)/2.

Таким образом, максимальное количество королей на доске можно выразить формулой:

• Если n четное: максимальное количество королей = (n²) / 2
• Если n нечетное: максимальное количество королей = (n² + 1) / 2

Это связано с тем, что для нечетных размеров доски, в центре будет находиться одна лишняя клетка, которую можно использовать для размещения короля.

Пример:

1. Для n = 1: 1 король. (1)
2. Для n = 2: 2 короля. (2)
3. Для n = 3: 5 королей. (5)
4. Для n = 4: 8 королей. (8)

С учетом вышеизложенного, в общем виде для любого n ваши вычисления будут выглядеть так:

def max_kings(n):
    return (n * n + 1) // 2

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

Таким образом, вы сможете правильно рассчитать максимальное количество королей для любого размера доски n.