Всё могут короли! Ограничение по времени: 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 баллов. Замечание Смотри рисунок: Ввод Вывод 3 4 Код Python 3 keyboard_arrow_down Код из файла

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

Король угрожает всем соседним клеткам, включая диагонали. Это означает, что он не может находиться ни в одной клетке, которая находится в пределах одной клетки по горизонтали, вертикали или диагонали от него.

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

Формула для подсчёта количества королей будет следующей:

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

Таким образом, общая формула будет выглядеть так:

\[ \text{количество королей} = \left\lceil \frac{n^2}{2} \right\rceil \]

На Python это можно реализовать следующим образом:

import math

n = int(input())
max_kings = (n * n + 1) // 2  # или использовать math.ceil(n * n / 2), но это более эффективно
print(max_kings)

Это решение эффективно, так как вычисления производятся за константное время \( O(1) \), и корректно работает при больших значениях \( n \) (до \( 10^9 \)). Убедитесь, что ваше вычисление выполняется с использованием типа данных, способного обрабатывать большие числа, таких как int в Python, который автоматически меняет размер.