Ворожі коні#13

Ворожі коні (Розбір)

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

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

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

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

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

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

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

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

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

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

Асимптотична складність:

Автор задачі:

Богдан Фейса

Задачу підготував:

Богдан Фейса, Павло Ціцей

Розбір написав:

Богдан Фейса