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

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

Каждый король окружает свои клетки по диагонали, по вертикали и по горизонтали, всего 8 клеток вокруг него (если они есть на доске).

Анализ задачи

При расстановке королей на шахматной доске:

1. Если n = 1, то на доске можно поставить 1 короля.
2. Если n = 2, то на доске также можно поставить 2 короля.
3. Если n = 3, то лучше всего поставить на клетки (1, 1) и (3, 3), итого 2 короля.
4. Если n = 4, можно поставить 4 короля на клетки (1, 1), (1, 3), (3, 1), и (3, 3).

Подход к вычислению

Лучший способ расставить королей — это чередовать их размещение в клетках. Например:

• На доске четного размера (n = 2k) можно расставить максимальное количество королей, используя половину клеток. Формула будет: \[ \text{Количество королей} = k^2 = \left(\frac{n}{2}\right)^2 \]
• На доске нечетного размера (n = 2k + 1) максимально количество можно вычислить аналогично, но с дополнительной клеткой: \[ \text{Количество королей} = (k + 1) * (k + 1) = \left(\frac{n + 1}{2}\right)^2 \]

Реализация в коде

Ниже представлен код для вычисления максимального количества королей:

def max_kings(n):
    if n % 2 == 0:
        return (n // 2) * (n // 2)
    else:
        return ((n // 2) + 1) * ((n // 2) + 1)

# Чтение входных данных
n = int(input().strip())
# Вывод результата
print(max_kings(n))

Объяснение

• Мы проверяем четность числа n.
• Если n четное, то мы используем целочисленное деление и берем квадрат этой половины.
• Если n нечетное, то мы увеличиваем целую часть на 1 и также берем квадрат.

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