많이 튼튼한 금고 테스트

지금 우리에게 ( N )층 빌딩과 새로 개발한 동일한 모델의 ( K )개 금고가 있다. 이 신형 금고의 견고함을 측정하려고 한다.

이 금고가 충격을 견디지 못하고 깨지기 시작하는 높이의 층을 ( F )층이라고 하자. 다시 말하면, ( F )층을 포함하여 그 위의 층에서 금고를 떨어뜨리면 무조건 부서지며, ( F )층의 아래층에서 금고를 떨어뜨리면 금고는 절대 부서지지 않는다. ( N )층에서도 부서지지 않을 수도 있으며, ( 1 )층에서도 부서질 수도 있다. 각각의 경우에 ( F ) 값은 각각 ( N+1 ), ( 1 )로 정해진다. ( F )의 값을 정확히 구해내면 견고함을 성공적으로 측정한 것으로 생각한다.

이 값을 정확히 구하기 위해 우리는 특정한 층에 올라가 직접 금고를 하나 떨어뜨려 보는 테스트를 할 수 있다. 모든 금고의 견고함은 동일하며, 금고가 부서졌으면 그 금고를 다음 테스트부터 다시 사용할 수 없고, 부서지지 않았다면 다시 사용할 수 있다.

우리는 이 ( N )층짜리 건물에서 ( K )개의 금고를 가지고 언제나 성공적으로 측정하기 위한 최소 테스트 횟수를 구하려고 한다.

예를 들어, ( N=10, K=1 )인 경우를 생각해보자. 만약 ( 4 )층에서 테스트를 시도하고 금고가 부서지지 않았다면 ( F )는 ( 5 ) 이상이란 결론이 나온다. 그러나 두 번째 테스트를 ( 6 )층에서 시도했을 때 금고가 부서졌다면 ( F )의 값이 ( 5 )일지 ( 6 )일지 모르는 상태에서 멀쩡한 금고가 없기 때문에 이 경우에는 ( F )값을 알아내는 데 실패한 경우가 된다. 따라서 최악의 상황에도 ( F )층을 정확히 알아내려면 ( 1 )층부터 ( 10 )층까지 차례대로 한 번씩 떨어뜨려 봐야 하므로 이 경우에는 ( 10 )회가 정답이 된다.

이번엔 금고가 하나 추가되어 ( N=10, K=2 )인 경우를 생각해보자. 만약 처음에 ( 4 )층에서 떨어뜨린다고 하면, 금고가 부서졌을 땐 ( 1, 2, 3 )층을 차례로 테스트해 봐야 하니 이때는 최대 ( 4 )번 테스트하게 된다. 그러나 금고가 부서지지 않았다면 다음번엔 ( 7 )층에서 테스트한다. 이때 부서졌다면 ( 5, 6 )층을 차례대로 시도하고, 부서지지 않았다면 세 번째 시도에 ( 9 )층을, 이때 부서졌다면 네 번째에 ( 8 )층을, 부서지지 않았다면 ( 10 )층을 시도하면 된다. 이 방법으로 테스트를 한다면 최악의 경우 ( 4 )번만에 정확한 ( F )값을 알 수 있고 이보다 더 적은 횟수로 가능한 모든 ( F )값을 정확히 측정해내기는 불가능하다.

두 정수 ( N, K )가 주어졌을 때 가능한 모든 ( F )의 값에 대해 정확히 측정해내기 위한 최소 테스트 횟수를 출력하시오.

첫째 줄에 정수 ( N(1\le N\le 10^{100}) )이 주어진다.

둘째 줄에 정수 ( K(1\le K\le N) )가 주어진다.

첫째 줄에 정확한 측정을 위해 필요한 최소 테스트 횟수를 출력한다.