시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 89 45 40 59.701%

문제

고전적인 '두 개의 유리 공' 문제는 다음과 같다:

두 개의 동일한 유리구가 있고, 100층 짜리 빌딩에서 유리구를 떨어뜨려서 깨지는 가장 낮은 층을 찾고 싶다. 유리구가 안깨진다면 아무런 피해가 없다고 가정하자. 어떻게 해야 (최악의 상황에서도) 가장 빨리 찾을 수 있을까?

우리가 오직 하나의 공이 있다고 가정하자. 그러면 우리는 1층부터 100층까지 차례대로 떨어뜨려보는 방법 밖에 없다.

최악의 경우는 100번만에 찾는 것이다.

이제 우리에게 두 개의 공이 있다고 하자. 그리고 첫 번째 공을 n층에서 떨어뜨린다고 하자. 만약에 그게 깨진다면 다시 공 하나가 있는 경우로 돌아가서, 1층부터 n-1층까지 시도해보면된다. 이 경우 최악의 경우 1+(n-1), 즉 n번의 시도만에 찾을 수 있다. 하지만 n층에서 깨지지 않았다면, n+1층에서 100층까지만 실험해보면 된다. 깨지거나 깨지지 않았거나 우리는 한 번의 시도를 하였다. 그래서 실험 횟수는 최악의 경우 모든 n에 대하여 가장 작다.

B개의 공과 M층 짜리 빌딩에서 최악의 경우에 몇 번 공을 떨어뜨려야 하는지를 계산하는 프로그램을 작성하시오.

입력

첫째 줄은 데이터 세트 수 P(1 ≤ P ≤ 1000)가 입력으로 들어온다. 각각의 데이터 세트는 한 줄로 구성되어 있으며 2개의 숫자가 공백으로 구분되어 있다. 유리공의 개수 B(1 ≤ B ≤ 50), 건물의 층 수 M(1 ≤ M ≤ 1000)

출력

각각의 데이터 세트에 대해 한 줄 씩, B, M에 대해 (최악의 경우에도)가장 적은 횟수의 시도 횟수를 공백으로 구분하여 출력한다.

예제 입력 1

4
2 10
2 100
2 300
25 900

예제 출력 1

4
14
24
10
W3sicHJvYmxlbV9pZCI6IjI2OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZjUiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YWNlMFx1YzgwNFx1YzgwMVx1Yzc3OCAmIzM5O1x1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzIwXHViOWFjIFx1YWNmNSYjMzk7IFx1YmIzOFx1YzgxY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0OjxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5cclxuXHRcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWM3MjBcdWI5YWNcdWFkNmNcdWFjMDAgXHVjNzg4XHVhY2UwLCAxMDBcdWNlMzUgXHVjOWRjXHViOWFjIFx1YmU0Y1x1YjUyOVx1YzVkMFx1YzExYyBcdWM3MjBcdWI5YWNcdWFkNmNcdWI5N2MgXHViNWE4XHVjNWI0XHViNzI4XHViODI0XHVjMTFjIFx1YWU2OFx1YzljMFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMGFlXHVjNzQwIFx1Y2UzNVx1Yzc0NCBcdWNjM2VcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWM3MjBcdWI5YWNcdWFkNmNcdWFjMDAgXHVjNTQ4XHVhZTY4XHVjOWM0XHViMmU0XHViYTc0IFx1YzU0NFx1YmIzNFx1YjdmMCBcdWQ1M2NcdWQ1NzRcdWFjMDAgXHVjNWM2XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yzc5MC4gXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU3NFx1YzU3YyAoXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YzBjMVx1ZDY2OVx1YzVkMFx1YzExY1x1YjNjNCkgXHVhYzAwXHVjN2E1IFx1YmU2OFx1YjlhYyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+XHJcblx0XHVjNmIwXHViOWFjXHVhYzAwIFx1YzYyNFx1YzljMSBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2Y1XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjdlY1x1YmE3NCBcdWM2YjBcdWI5YWNcdWIyOTQgMVx1Y2UzNVx1YmQ4MFx1ZDEzMCAxMDBcdWNlMzVcdWFlNGNcdWM5YzAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YjVhOFx1YzViNFx1YjcyOFx1YjgyNFx1YmNmNFx1YjI5NCBcdWJjMjlcdWJjOTUgXHViYzE2XHVjNWQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG48cD5cclxuXHRcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwXHViMjk0IDEwMFx1YmM4OFx1YjljY1x1YzVkMCBcdWNjM2VcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzRcdWM4MWMgXHVjNmIwXHViOWFjXHVjNWQwXHVhYzhjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVhY2Y1XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWNmNVx1Yzc0NCBuXHVjZTM1XHVjNWQwXHVjMTFjIFx1YjVhOFx1YzViNFx1YjcyOFx1YjliMFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWFkZjhcdWFjOGMgXHVhZTY4XHVjOWM0XHViMmU0XHViYTc0IFx1YjJlNFx1YzJkYyBcdWFjZjUgXHVkNTU4XHViMDk4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzAwXHVjMTFjLCAxXHVjZTM1XHViZDgwXHVkMTMwIG4tMVx1Y2UzNVx1YWU0Y1x1YzljMCBcdWMyZGNcdWIzYzRcdWQ1NzRcdWJjZjRcdWJhNzRcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWFjYmRcdWM2YjAgXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMCAxKyhuLTEpLCBcdWM5ODkgblx1YmM4OFx1Yzc1OCBcdWMyZGNcdWIzYzRcdWI5Y2NcdWM1ZDAgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBuXHVjZTM1XHVjNWQwXHVjMTFjIFx1YWU2OFx1YzljMFx1YzljMCBcdWM1NGFcdWM1NThcdWIyZTRcdWJhNzQsIG4rMVx1Y2UzNVx1YzVkMFx1YzExYyAxMDBcdWNlMzVcdWFlNGNcdWM5YzBcdWI5Y2MgXHVjMmU0XHVkNWQ4XHVkNTc0XHViY2Y0XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVhZTY4XHVjOWMwXHVhYzcwXHViMDk4IFx1YWU2OFx1YzljMFx1YzljMCBcdWM1NGFcdWM1NThcdWFjNzBcdWIwOTggXHVjNmIwXHViOWFjXHViMjk0IFx1ZDU1YyBcdWJjODhcdWM3NTggXHVjMmRjXHViM2M0XHViOTdjIFx1ZDU1OFx1YzYwMFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YzJlNFx1ZDVkOCBcdWQ2OWZcdWMyMThcdWIyOTQgXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMCBcdWJhYThcdWI0ZTAgblx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0Qlx1YWMxY1x1Yzc1OCBcdWFjZjVcdWFjZmMgTVx1Y2UzNSBcdWM5ZGNcdWI5YWMgXHViZTRjXHViNTI5XHVjNWQwXHVjMTFjIFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHViYTg3IFx1YmM4OCBcdWFjZjVcdWM3NDQgXHViNWE4XHVjNWI0XHViNzI4XHViODI0XHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzQwIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjggXHVjMjE4IFAoMSAmbGU7IFAgJmxlOyAxMDAwKVx1YWMwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAgMlx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzcyMFx1YjlhY1x1YWNmNVx1Yzc1OCBcdWFjMWNcdWMyMTggQigxICZsZTsgQiAmbGU7IDUwKSwgXHVhYzc0XHViYjNjXHVjNzU4IFx1Y2UzNSBcdWMyMTggTSgxICZsZTsgTSAmbGU7IDEwMDApPFwvcD5cclxuXHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0IFx1YzUyOSwgQiwgTVx1YzVkMCBcdWIzMDBcdWQ1NzQgKFx1Y2Q1Y1x1YzU0NVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIzYzQpXHVhYzAwXHVjN2E1IFx1YzgwMVx1Yzc0MCBcdWQ2OWZcdWMyMThcdWM3NTggXHVjMmRjXHViM2M0IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFsbHMgIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY2xhc3NpYyBUd28gR2xhc3MgQmFsbHMgYnJhaW4tdGVhc2VyIGlzIG9mdGVuIHBvc2VkIGFzOiZuYnNwOzxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5cclxuPHA+JnF1b3Q7R2l2ZW4gdHdvIGlkZW50aWNhbCBnbGFzcyBzcGhlcmVzLCB5b3Ugd291bGQgbGlrZSB0byBkZXRlcm1pbmUgdGhlIGxvd2VzdCBmbG9vciBpbiBhIDEwMC1zdG9yeSBidWlsZGluZyBmcm9tIHdoaWNoIHRoZXkgd2lsbCBicmVhayB3aGVuIGRyb3BwZWQuIEFzc3VtZSB0aGUgc3BoZXJlcyBhcmUgdW5kYW1hZ2VkIHdoZW4gZHJvcHBlZCBiZWxvdyB0aGlzIHBvaW50LiBXaGF0IGlzIHRoZSBzdHJhdGVneSB0aGF0IHdpbGwgbWluaW1pemUgdGhlIHdvcnN0LWNhc2Ugc2NlbmFyaW8gZm9yIG51bWJlciBvZiBkcm9wcz8mcXVvdDsmbmJzcDs8XC9wPlxyXG48XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+U3VwcG9zZSB0aGF0IHdlIGhhZCBvbmx5IG9uZSBiYWxsLiBXZSYjMzk7ZCBoYXZlIHRvIGRyb3AgZnJvbSBlYWNoIGZsb29yIGZyb20gMSB0byAxMDAgaW4gc2VxdWVuY2UsIHJlcXVpcmluZyAxMDAgZHJvcHMgaW4gdGhlIHdvcnN0IGNhc2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdyBjb25zaWRlciB0aGUgY2FzZSB3aGVyZSB3ZSBoYXZlIHR3byBiYWxscy4gU3VwcG9zZSB3ZSBkcm9wIHRoZSBmaXJzdCBiYWxsIGZyb20gZmxvb3Igbi4gSWYgaXQgYnJlYWtzIHdlJiMzOTtyZSBpbiB0aGUgY2FzZSB3aGVyZSB3ZSBoYXZlIG9uZSBiYWxsIHJlbWFpbmluZyBhbmQgd2UgbmVlZCB0byBkcm9wIGZyb20gZmxvb3JzIDEgdG8gbi0xIGluIHNlcXVlbmNlLCB5aWVsZGluZyBuIGRyb3BzIGluIHRoZSB3b3JzdCBjYXNlICh0aGUgZmlyc3QgYmFsbCBpcyBkcm9wcGVkIG9uY2UsIHRoZSBzZWNvbmQgYXQgbW9zdCBuLTEgdGltZXMpLiBIb3dldmVyLCBpZiBpdCBkb2VzIG5vdCBicmVhayB3aGVuIGRyb3BwZWQgZnJvbSBmbG9vciBuLCB3ZSBoYXZlIHJlZHVjZWQgdGhlIHByb2JsZW0gdG8gZHJvcHBpbmcgZnJvbSBmbG9vcnMgbisxIHRvIDEwMC4gSW4gZWl0aGVyIGNhc2Ugd2UgbXVzdCBrZWVwIGluIG1pbmQgdGhhdCB3ZSYjMzk7dmUgYWxyZWFkeSB1c2VkIG9uZSBkcm9wLiBTbyB0aGUgbWluaW11bSBudW1iZXIgb2YgZHJvcHMsIGluIHRoZSB3b3JzdCBjYXNlLCBpcyB0aGUgbWluaW11bSBvdmVyIGFsbCBuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3Ugd2lsbCB3cml0ZSBhIHByb2dyYW0gdG8gZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIG51bWJlciBvZiBkcm9wcyByZXF1aXJlZCwgaW4gdGhlIHdvcnN0IGNhc2UsIGdpdmVuIEIgYmFsbHMgYW5kIGFuIE0tc3RvcnkgYnVpbGRpbmcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhyZWUgKDMpIGRlY2ltYWwgaW50ZWdlciB2YWx1ZXM6IHRoZSBwcm9ibGVtIG51bWJlciwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIG51bWJlciBvZiBiYWxscyBCLCAoMSAmbGU7IEIgJmxlOyA1MCksIGZvbGxvd2VkIGJ5IGEgc3BhY2UgYW5kIHRoZSBudW1iZXIgb2YgZmxvb3JzIGluIHRoZSBidWlsZGluZyBNLCAoMSAmbGU7IE0gJmxlOyAxMDAwKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgZ2VuZXJhdGUgb25lIGxpbmUgb2Ygb3V0cHV0IHdpdGggdGhlIGZvbGxvd2luZyB2YWx1ZXM6IFRoZSBkYXRhIHNldCBudW1iZXIgYXMgYSBkZWNpbWFsIGludGVnZXIsIGEgc3BhY2UsIGFuZCB0aGUgbWluaW11bSBudW1iZXIgb2YgZHJvcHMgbmVlZGVkIGZvciB0aGUgY29ycmVzcG9uZGluZyB2YWx1ZXMgb2YgQiBhbmQgTS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=