Testing a Very Sturdy Safe

We have an ( N )-story building and ( K ) safes of the same newly developed model. We want to measure how sturdy this new safe is.

Let ( F ) be the floor height at which the safe starts to break under impact. In other words, if the safe is dropped from floor ( F ) or any floor above it, it always breaks, and if it is dropped from a floor below ( F ), it never breaks. It may survive a drop from floor ( N ), and it may break even when dropped from floor ( 1 ). In those cases ( F ) is defined as ( N+1 ) and ( 1 ), respectively. We consider the sturdiness successfully measured when we determine the value of ( F ) exactly.

To determine this value exactly, we can go up to a specific floor and drop one safe ourselves. Every safe has the same sturdiness. If a safe breaks, we cannot use it again in later tests; if it does not break, we can use it again.

Given this ( N )-story building and ( K ) safes, we want to find the minimum number of tests that always succeeds in measuring the sturdiness.

For example, consider ( N=10, K=1 ). If we test from floor ( 4 ) and the safe does not break, we conclude that ( F ) is at least ( 5 ). But if we then test from floor ( 6 ) and the safe breaks, we do not know whether ( F ) is ( 5 ) or ( 6 ), and we have no intact safe left, so this attempt fails to determine ( F ). Therefore, to determine floor ( F ) exactly even in the worst case, we must drop a safe from floor ( 1 ) through floor ( 10 ) one at a time, so the answer here is ( 10 ) tests.

Now consider ( N=10, K=2 ), with one more safe. If we drop a safe from floor ( 4 ) first and it breaks, we must test floors ( 1, 2, 3 ) in order, for at most ( 4 ) tests. But if it does not break, we test floor ( 7 ) next. If it breaks there, we try floors ( 5, 6 ) in order; if it does not break, we try floor ( 9 ) on the third test, and if it breaks there, we try floor ( 8 ) on the fourth test, while if it does not break, we try floor ( 10 ). With this method we can learn the exact value of ( F ) in at most ( 4 ) tests in the worst case, and it is impossible to measure every possible value of ( F ) exactly with fewer tests.

Given two integers ( N ) and ( K ), output the minimum number of tests needed to measure every possible value of ( F ) exactly.

The first line contains the integer ( N(1\le N\le 10^{100}) ).

The second line contains the integer ( K(1\le K\le N) ).

On the first line, output the minimum number of tests needed for an exact measurement.