Problem G
Maximum Choice
Bryan is a passenger on a voyage to a distant planet. Like the other passengers he awaits in cryosleep. However, due to a malfunction he awoke early and finds himself awake and alone. The ship’s sophisticated navigation AI, ChatHAL, is responsible for waking passengers.
It appears that ChatHAL wants to play a game with Bryan. The game is simple: ChatHAL has hidden the key to his cryopod beneath one of the other pods. It is Bryan’s job to guess and find that pod and retrieve the key to go back to cryosleep.
There are $n$ cryopods on the ship, all lined up in a single file. ChatHAL tells Bryan he is able to make up to $b$ guesses per turn. He can guess the same pod multiple times if he wants to. Bryan plays his first turn of the game, and guesses up to $b$ pods. If the key is underneath one of the pods Bryan guessed, then he wins. Otherwise, ChatHAL will tell Bryan which two pods enclose the smallest region containing the key. The endpoints of this region must each be either a pod that Bryan guessed, or the first or last pod in the line. Bryan then proceeds on to his second turn, where he makes up to another $b$ guesses once again. This process repeats until Bryan finds the key.
There is a slight problem however: $n$ can be as large as $2^{63}-1$, so Bryan is looking to be efficient to avoid searching the entire ship. What is the most amount of turns, in the worst case, that Bryan would have to play if he played optimally?
Input
Input consists of the space-separated integers $1 \leq n < 2^{63}$ and $1 \leq b \leq 15$.
Output
Return the maximum amount of attempts Bryan would need if he guessed optimally.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 1 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1000 2 |
7 |
