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

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

При оптимальном размещении королей можно определить, что короли могут занимать клетки, расположенные на определённом расстоянии друг от друга. Например, если мы обозначим клетки, на которых могут располагаться короли, то они могут занимать клетки первоначально по «черным» или «белым» клеткам, как на стандартной шахматной доске, но для максимизации их количества размещаем их с шагом в 2.

Подсчет королей

1. Для доски размером \( n \):
   • Если \( n \) четное, то можно разместить \( \frac{n \times n}{2} \) королей.
   • Если \( n \) нечетное, то в этом случае количество размещаемых королей составляет \( \frac{n \times n + 1}{2} \). Это связано с тем, что в нечетной сетке останется одна лишняя клетка, которая также может быть занята.

Формула

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

\[ k = \left\lceil \frac{n^2}{2} \right\rceil \]

где \( \left\lceil x \right\rceil \) — это округление вверх.

Для удобства расчета с целыми числами можно использовать:

\[ k = \frac{n \times n + 1}{2} \]

Пример реализации

Вот пример, как это можно реализовать на Python:

n = int(input().strip())
k = (n * n + 1) // 2
print(k)

Итог

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