Газон у Потоколяндії#137

Газон у Потоколяндії (Editorial)

Ключ до задачі — у правилі відростання. Козак косить ділянку, повністю вкриту травою; дія триває годину, а рівно через годину після її завершення трава там виростає знову. Отже, у момент, коли починається наступна дія, щойно скошена ділянка ще гола — тому дві послідовні дії мусять бути неперетинними. А от через дію ділянку вже можна косити повторно.

Розберемо випадки.

Якщо n = k, вистачає однієї дії: косимо весь газон за одну годину.

Якщо n \ge 2k, жодних перешкод немає. Скосивши ділянку , ми залишаємо праворуч смугу довжини n - k \ge k, у якій одразу поміщається наступна неперетинна ділянка. Рухаючись так далі, ми ніколи не змушені чекати, і відповідь дорівнює мінімальній кількості відрізків довжини , потрібних для покриття, тобто

\left\lceil \frac{n}{k} \right\rceil.

Найцікавіший випадок — k < n < 2k. Тут двох дій достатньо для покриття, але будь-які дві ділянки довжини у газоні довжини n < 2k обов'язково перетинаються, тому виконати їх поспіль не можна. Не можна й вставити між ними якусь третю ділянку: вільної трави залишається лише n - k < k метрів. Отже, Козаку доведеться просто перечекати одну годину, доки трава відросте, і аж тоді скосити другу половину. Разом виходить

години: година на першу дію, година очікування і година на другу.

Тому підсумкова відповідь: , якщо k < n < 2k, і у решті випадків.