Description

Suppose that OO lab develops and sells an iron suit with special functions that enable the user to jump K spaces forward at once or teleport to the location of (current distance from start) x 2. This iron suit works with a battery whose power level does not decrease for teleportation but uses K amount of power to jump K spaces forward. Therefore, teleporting is a more efficient way to move with the iron suit. A purchaser of the iron suit wants to move to the location of N distance from here using the suit. However, to minimize battery usage, the purchaser wants to minimize the number of jumps. Given the distance to move by the purchaser N as the parameter, write a function "solution" to return the minimum required power level to use.

For example, the purchaser wants to move to a location 5 spaces away from here.
There are several ways to move to the location 5 spaces away using the iron suit.

  • Jumping 5 spaces forward from the initial location 0 will allow the purchaser to arrive at once but 5 power levels would be required.
  • Jumping 2 spaces forward from the initial location 0 and then teleporting, the purchaser will move to location 4 (current distance from start : 2) x 2. The purchaser can move to location 5 by jumping 1 space forward. Therefore, a total of 3 power levels are required.
  • Jumping 1 space forward from the initial location 0 and then teleporting, the purchaser will move to location 2 (current distance from start : 1) x 2. Teleporting again, the purchaser will move to location 4 (current distance from start : 2) x 2. The purchaser can move to location 5 by jumping 1 space forward. Therefore, a total of 2 power levels are required.

Among the 3 cases above, the third case uses the least power level to move 5 spaces. Therefore, the answer is 2.

Constraints
  • Number N: A natural number between 1 and 1,000,000,000.
  • Number K: A natural number.
Examples
N result
5 2
6 2
5000 5

Example #1
It is the same as the example in the problem statement.

Example #2
Jumping 1 space forward from the initial location 0 and then teleporting, the purchaser will move to location 2 (current distance from start : 1) x 2. The purchaser can move to location 3 by jumping 1 space forward. By teleporting again, the purchaser will arrive at location 6 (current distance from start : 3) x 2. As this example requires the least amount of power level, return 2.

Example #3
Similar to example #2.

Result Stop
Result of [Run] or [Submit] will be displayed here