Перший ключовий факт:
Коні завжди б'ють клітинки протилежного кольору до того, на якій стоять
Другий ключовий факт:
При 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
Асимптотична складність:
Автор задачі: | Богдан Фейса |
Задачу підготував: | Богдан Фейса, Павло Ціцей |
Розбір написав: | Богдан Фейса |