Всё могут короли! Ограничение по времени:1 секунда Ограничение по памяти: 256 мегабайт Не могут они только стоять рядом друг с другом на шахматной доске(даже по диагонали). По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно. Формат входных данных Единственная строка входного файла содержит одно натуральное число n (1≤n≤10⁹) - размер квадратной шахматной доски. Формат входных данных Введите одно натуральное число -ответ на вопрос задачи. Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64-битный тип данных.
Чтобы решить задачу об оптимальном размещении королей на шахматной доске размером \( n \times n \), важно помнить, что каждый король атакует свои соседние клетки, включая диагонали. Это ограничивает возможности размещения новых королей рядом с уже стоящими.
Наиболее эффективным способом расстановки королей является использование шахматной доски, где короли располагаются на черных или белых клетках. Если расставить королей на клетках одного цвета, они не будут угрожать друг другу.
Для доски размером \( n \) можно вычислить максимальное количество королей следующим образом:
Если размер \( n \) чётный: на такой доске будет равное количество черных и белых клеток. Таким образом, максимальное количество королей будет равно \( \frac{n^2}{2} \).
Если размер \( n \) нечётный: на ней будет чуть больше клеток одного цвета. В этом случае количество королей составляет \( \frac{n^2 + 1}{2} \) (где деление происходит с округлением вниз).
Таким образом, формула для расчета максимального количества королей будет выглядеть так:
\[ \text{max\_королей} = \left\lfloor \frac{n^2 + 1}{2} \right\rfloor \]
Теперь можно представить ответ в виде одной строки кода:
def max_kings(n):
return (n * n + 1) // 2
Для любого введенного натурального числа \( n \), эта функция выдаст максимальное количество королей, которых можно расставить на шахматной доске.
Так что, если вам дано число \( n \), просто подставьте его в данную формулу, чтобы получить ответ.
