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

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

Одним из эффективных способов для размещения королей является использование шахматной доски в виде "черно-белых" клеток. Можно разместить королей только на клетках одного цвета, что значительно уменьшает количество конфликтных позиций.

Решение

На доске размером n x n можно установить королей следующим образом:

1. Если n четное, общее количество клеток равно n^2. Половина из них будет одного цвета, а другая половина — другого. Таким образом, максимальное количество королей можно разместить в клетках одного цвета: \( \frac{n^2}{2} \).

2. Если n нечетное, тогда общее количество клеток также равно n^2, и количество клеток будет распределено так, что на одной "черной" клетке будет на одну клетку больше, чем на "белой". В этом случае максимальное количество королей можно разместить таким образом: \( \frac{n^2 + 1}{2} \).

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

#include <stdio.h>

int main() {
    long long n;
    scanf("%lld", &n);  // Ввод n
    long long max_kings;

    if (n % 2 == 0) {
        max_kings = (n * n) / 2;
    } else {
        max_kings = (n * n + 1) / 2;
    }

    printf("%lld\n", max_kings);  // Вывод результата
    return 0;
}

Пояснение кода:

1. Мы используем scanf для чтения размера доски n.
2. В зависимости от четности n вычисляем максимальное количество королей:
   • Если n четное, то делим \( n^2 \) на 2.
   • Если n нечетное, прибавляем 1 к \( n^2 \) и делим на 2.
3. Затем выводим результат.

Этот алгоритм работает за O(1) времени, что соответствует ограничению по времени в 1 секунду, и использует O(1) памяти, что также удовлетворяет условию.