Всё могут короли! Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По…
Всё могут короли! Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Не могут они только стоять рядом друг с другом на шахматной доске (даже по диагонали). По размеру доски определите наибольшее количество королей, которое можно на ней расставить так, чтобы ещё одного короля поставить было невозможно. Формат входных данных Единственная строка входного файла содержит одно натуральное число п (1 < n ≤ 10%) - размер квадратной шахматной доски. Формат выходных данных Выведите одно натуральное число — ответ на вопрос задачи. Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64 -битный тип данных, например, long long в C++, int64 в Free Pascal, long B Java. Система оценки Решения, верно работающие при 1 I n ≤ 100, получат не менее 30 баллов. Решения, верно работающие при 1 In ≤ 105 , получат не менее 60 баллов. Замечание Смотри рисунок: 2 3 Ввод Вывод 3 4 Код 1 2 3 Python 3 Код из файла
Для решения задачи о расстановке королей на шахматной доске так, чтобы они не могли угрожать друг другу, можно использовать следующий подход. Короли не могут находиться на смежных клетках, включая диагонали. Мы можем использовать шахматную доску размером \(n \times n\) и разместить королей в определенной конфигурации.
Наиболее эффективный способ разместить королей — это использовать шахматную раскладку на черные и белые клетки. Королей можно размещать только на клетках одного цвета.
При этом, чтобы не было возможности поставить еще одного короля, нужно добиться следующей конфигурации:
- Если \(n\) четное, то максимальное количество королей будет равно \( \frac{n^2}{2} \).
- Если \(n\) нечетное, то максимальное количество королей будет равно \( \frac{n^2}{2} + 1 \).
Теперь можно написать код на Python для подсчета максимального количества королей:
def max_kings(n):
if n % 2 == 0:
return (n * n) // 2
else:
return (n * n) // 2 + 1
n = int(input())
print(max_kings(n))
Как работает код:
- Сначала мы проверяем, четное число \(n\) или нет.
- Если четное, вычисляем \( \frac{n^2}{2} \).
- Если нечетное - вычисляем \( \frac{n^2}{2} + 1 \).
- Результат выводится на печать.
Пример:
Для \(n = 3\):
- \( \frac{3^2}{2} + 1 = 4 \)
Для \(n = 4\):
- \( \frac{4^2}{2} = 8 \)
Оба случая соответствуют максимальному количеству королей, которых можно расставить на доске.
