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

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

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

Ну вот как это сделать:

1. Для чётного n можно разместить королей на всех клетках одного цвета (чёрные или белые), что составляет ровно половину клеток доски:

   • Количество королей = (n * n) / 2.

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

   • Количество королей = (n * n + 1) / 2.

Выражая это формально, можно использовать формулу:

• \( \text{max\_kings}(n) = \left\lceil \frac{n^2}{2} \right\rceil \)

В Python это можно записать как:

import math

def max_kings(n):
    return math.ceil(n * n / 2)

n = int(input())
print(max_kings(n))

Теперь, если мы применим это к вашему пределу \(1 < n < 10^9\), наш алгоритм все равно работает за O(1) времени, так как мы просто вычисляем значение на основе n. Данная формула обеспечит правильный ответ для любого допустимого значения n.