P15046 [UOI 2022 II Stage] Magic Shoes

Friends of Cossack Moustache received that secret letter. It turned out that inside there was a blueprint for a pair of ancient magic shoes. These magic shoes allow the wearer to accelerate to an amazing speed. The wearer’s initial speed is $1$ meter per second. If the current speed of the person wearing the magic shoes is $a$ meters per second, then she can cast one of the following two spells: - Increase her speed by $a$ meters per second. - Increase her speed by $a+1$ meters per second. What is the minimum number of spells she needs to cast to increase her speed exactly to $k$ meters per second?

The first line contains an integer $k$ ($1 \leq k \leq 10^{18}$), the target speed to reach. It is guaranteed that the given speed can be reached in a finite number of steps.

Output one number, the minimum number of spells needed to reach the given speed.

In the first sample, the initial speed is already $1$, so no spells are needed. In the second sample, you can use the first spell, so the speed increases by $1$ meter per second and becomes exactly $2$ meters per second. In the third sample, you can use the first spell, then the second spell, then the first spell. The speed changes as follows: $1 \rightarrow 2 \rightarrow 5 \rightarrow 10$. It can be proven that the number of spells needed to reach this speed cannot be smaller. Translated by ChatGPT 5