Ворожі коні

Перший ключовий факт:

- Коні завжди б'ють клітинки протилежного кольору до того, на якій стоять

Другий ключовий факт:

- При $$$n\ne2$$$ нам вигідно розмістити всіх конів на клітинках одного кольору

Для отримання максимальної кількості конів які ми можемо розмістити на одній дошці при $$$n \ne 2$$$, порахуємо кількість клітинок кожного кольору:

- Чорні клітинки: $$$\lfloor \frac{n^2}{2} \rfloor $$$

- Білі клітинки: $$$\lceil \frac{n^2}{2} \rceil$$$

Коли ж $$$n = 2$$$, ми можемо розмістити конів у всіх $$$n^2$$$ клітках, через те, що ні один не зможе дістати до іншого.

Тепер маючи максимальну кількість конів, яку ми можемо розмістити на одній дошці $$$max$$$, кількість дощок які потрібно для того, щоб розмістити $$$K$$$ конів знаходиться за формулою:

$$$re=\lceil \frac{K}{max} \rceil$$$

Асимптотична складність: $$$O(1)$$$

Автор задачі: | Богдан Фейса
Задачу підготував: | Богдан Фейса, Павло Ціцей
Розбір написав: | Богдан Фейса