\begin{tutorial}{Козак Вус та чарівні черевики}

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

Намалюємо дерево з направленими вниз ребрами та коренем у вершині 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)$.




\end{tutorial}
