Всё могут короли! Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). 👉По…
Всё могут короли! Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). 👉По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно. Формат входных данных Единственная строка входного файла содержит одно натуральное число n (1 ≤ n ≤ 10%) - размер квадратной шахматной доски. Формат выходных данных Выведите одно натуральное число — ответ на вопрос задачи. 👉Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64-битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java. Система оценки 👉Решения, верно работающие при 1 ≤ n ≤ 100, получат не менее 30 баллов. 👉Решения, верно работающие при 1 ≤ n ≤ 10%, получат не менее 60 баллов.
Чтобы разместить максимальное количество королей на шахматной доске размером n x n так, чтобы они не угрожали друг другу, необходимо учитывать, что каждый король контролирует всю свою клетку и клетки, расположенные вокруг него (это 8 клеток по соседству).
Для минимизации угрозы от королей, мы можем разместить их по шахматному принципу: на одну клетку подряд по горизонтали и вертикали (черные и белые клетки). Оптимальная расстановка королей будет состоять в том, чтобы размещать их на клетках одного цвета.
Если мы рассмотрим доску с четным размером n (например, 2, 4, 6 и т. д.), то:
- На черных клетках будет 𝑛²/2 королей.
- На белых клетках будет 𝑛²/2 королей.
Если n — нечетное число, то:
- На одной из цветов клеток будет (𝑛² + 1) / 2 королей.
- На другой — (𝑛² - 1) / 2 королей.
Таким образом, максимальное количество королей K, которое можно разместить на доске будет вычисляться как:
- Если n четное: K = n² / 2.
- Если n нечетное: K = (n² + 1) / 2.
Теперь можно сделать код для этой задачи. Вот пример на Python:
n = int(input())
if n % 2 == 0:
print(n * n // 2)
else:
print((n * n + 1) // 2)
Этот код принимает значение n и, в зависимости от его четности, вычисляет максимальное количество королей, которое можно расставить на черных или белых клетках, не угрожая друг другу.
Теперь, если у вас возникнут дополнительные вопросы по данной теме или другим задачам, не стесняйтесь задавать!
