Построение с общими разрезами

Выбираем степени двойки по убыванию, начиная с наибольшей, строго меньшей LL. На каждом ходе от всех кусков, которые длиннее выбранной степени двойки, отрезаем эту одинаковую целую длину. После этого каждый кусок не длиннее выбранной степени. На следующем ходе степень уменьшается вдвое, и каждый кусок снова требует не больше одного разреза. Последняя степень равна единице. Получаем ровно ⌈log⁡2L⌉\left\lceil \log_{2}L\right\rceil ходов и все единичные части.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 2. Выбираем степени двойки по убыванию, начиная с наибольшей, строго меньшей LL. На каждом ходе от всех кусков, которые длиннее выбранной степени двойки, отрезаем эту одинаковую целую длину. После этого каждый кусок не длиннее выбранной степени. На следующем ходе степень уменьшается вдвое, и каждый кусок снова требует не больше одного разреза. Последняя степень равна единице. Получаем ровно ⌈log⁡2L⌉\left\lceil \log_{2}L\right\rceil ходов и все единичные части.

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу