Козак Вус та чарівні черевики

Автор та розробник: Андрій Романов

Намалюємо дерево з направленими вниз ребрами та коренем у вершині 1, яке буде зображати всі можливі комбінації застосування заклять. З вершини $$$x$$$ можна перейти вниз у вершини $$$2 \cdot x$$$ та $$$2 \cdot x+1$$$, адже, маючи швидкість $$$x$$$ метрів на секунду, за допомогою одного закляття швидкість може стати рівною $$$x+x=2 \cdot x$$$ метри на секунду або $$$x+(x+1)=2 \cdot x+1$$$ метри на секунду. Кожен раз, спускаючись вниз, від кореня ми переходимо або в лівий вузол, тобто застосовуємо перше закляття або в правий вузол — застосовуємо друге закляття. Кожна вершина зустрічатиметься рівно один раз, а отже порядок застосування заклять, щоб потрапити з вершини $$$1$$$ у вершину $$$x$$$ єдиний, причому необхідна кількість заклять рівна відстані від $$$1$$$ до $$$x$$$. Помітимо, що на відстані $$$0$$$ від кореня знаходиться вершина $$$1$$$, на відстані $$$1$$$: $$$2$$$, $$$3$$$, на відстані $$$2$$$: $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, на відстані $$$3$$$: $$$8$$$, $$$9$$$, $$$10$$$, $$$11$$$, $$$12$$$, $$$13$$$, $$$14$$$, $$$15$$$ і так далі. Тобто на відстані $$$n$$$ від кореня знаходяться числа від $$$2^n$$$ до $$$2^{n+1}-1$$$, і щоб їх досягти ми відповідно застосуємо закляття $$$n$$$ разів.

Отже, якщо $$$2^n \leq k \leq 2^{n+1}-1$$$, то відповідь $$$n$$$. Інакше кажучи, $$$n = \lfloor \log k \rfloor$$$. Складність розв'язку $$$O(\log k)$$$.