시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblxyXG48cD5cclxuXHRcdWM3NzRcdWM4MWMgXHVjNmIwXHViOWFjXHVjNWQwXHVhYzhjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVhY2Y1XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNjYWJcdWJjODhcdWM5ZjggXHVhY2Y1XHVjNzQ0IG5cdWNlMzVcdWM1ZDBcdWMxMWMgXHViNWE4XHVjNWI0XHViNzI4XHViOWIwXHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHViOWNjXHVjNTdkXHVjNWQwIFx1YWRmOFx1YWM4YyBcdWFlNjhcdWM5YzRcdWIyZTRcdWJhNzQgXHViMmU0XHVjMmRjIFx1YWNmNSBcdWQ1NThcdWIwOThcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWFjMDBcdWMxMWMsIDFcdWNlMzVcdWJkODBcdWQxMzAgbi0xXHVjZTM1XHVhZTRjXHVjOWMwIFx1YzJkY1x1YjNjNFx1ZDU3NFx1YmNmNFx1YmE3NFx1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMCBcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwIDErKG4tMSksIFx1Yzk4OSBuXHViYzg4XHVjNzU4IFx1YzJkY1x1YjNjNFx1YjljY1x1YzVkMCBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIG5cdWNlMzVcdWM1ZDBcdWMxMWMgXHVhZTY4XHVjOWMwXHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNFx1YmE3NCwgbisxXHVjZTM1XHVjNWQwXHVjMTFjIDEwMFx1Y2UzNVx1YWU0Y1x1YzljMFx1YjljYyBcdWMyZTRcdWQ1ZDhcdWQ1NzRcdWJjZjRcdWJhNzQgXHViNDFjXHViMmU0LiBcdWFlNjhcdWM5YzBcdWFjNzBcdWIwOTggXHVhZTY4XHVjOWMwXHVjOWMwIFx1YzU0YVx1YzU1OFx1YWM3MFx1YjA5OCBcdWM2YjBcdWI5YWNcdWIyOTQgXHVkNTVjIFx1YmM4OFx1Yzc1OCBcdWMyZGNcdWIzYzRcdWI5N2MgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVjMmU0XHVkNWQ4IFx1ZDY5Zlx1YzIxOFx1YjI5NCBcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwIFx1YmFhOFx1YjRlMCBuXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBcdWFjMDBcdWM3YTUgXHVjNzkxXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRCXHVhYzFjXHVjNzU4IFx1YWNmNVx1YWNmYyBNXHVjZTM1IFx1YzlkY1x1YjlhYyBcdWJlNGNcdWI1MjlcdWM1ZDBcdWMxMWMgXHVjZDVjXHVjNTQ1XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWJhODcgXHViYzg4IFx1YWNmNVx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI4MjRcdWM1N2MgXHVkNTU4XHViMjk0XHVjOWMwXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOFx1YzkwNFx1Yzc0MCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4IFx1YzIxOCBQKDEgJmxlOyBQICZsZTsgMTAwMClcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWIyOTQgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwIDJcdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM3MjBcdWI5YWNcdWFjZjVcdWM3NTggXHVhYzFjXHVjMjE4IEIoMSAmbGU7IEIgJmxlOyA1MCksIFx1YWM3NFx1YmIzY1x1Yzc1OCBcdWNlMzUgXHVjMjE4IE0oMSAmbGU7IE0gJmxlOyAxMDAwKTxcL3A+XHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDFcdWFjMDFcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTVjIFx1YzkwNCBcdWM1MjksIEIsIE1cdWM1ZDAgXHViMzAwXHVkNTc0IChcdWNkNWNcdWM1NDVcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViM2M0KVx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVkNjlmXHVjMjE4XHVjNzU4IFx1YzJkY1x1YjNjNCBcdWQ2OWZcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjY5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhbGxzICIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNsYXNzaWMgVHdvIEdsYXNzIEJhbGxzIGJyYWluLXRlYXNlciBpcyBvZnRlbiBwb3NlZCBhczombmJzcDs8XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+XHJcbjxwPiZxdW90O0dpdmVuIHR3byBpZGVudGljYWwgZ2xhc3Mgc3BoZXJlcywgeW91IHdvdWxkIGxpa2UgdG8gZGV0ZXJtaW5lIHRoZSBsb3dlc3QgZmxvb3IgaW4gYSAxMDAtc3RvcnkgYnVpbGRpbmcgZnJvbSB3aGljaCB0aGV5IHdpbGwgYnJlYWsgd2hlbiBkcm9wcGVkLiBBc3N1bWUgdGhlIHNwaGVyZXMgYXJlIHVuZGFtYWdlZCB3aGVuIGRyb3BwZWQgYmVsb3cgdGhpcyBwb2ludC4gV2hhdCBpcyB0aGUgc3RyYXRlZ3kgdGhhdCB3aWxsIG1pbmltaXplIHRoZSB3b3JzdC1jYXNlIHNjZW5hcmlvIGZvciBudW1iZXIgb2YgZHJvcHM/JnF1b3Q7Jm5ic3A7PFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlN1cHBvc2UgdGhhdCB3ZSBoYWQgb25seSBvbmUgYmFsbC4gV2UmIzM5O2QgaGF2ZSB0byBkcm9wIGZyb20gZWFjaCBmbG9vciBmcm9tIDEgdG8gMTAwIGluIHNlcXVlbmNlLCByZXF1aXJpbmcgMTAwIGRyb3BzIGluIHRoZSB3b3JzdCBjYXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3cgY29uc2lkZXIgdGhlIGNhc2Ugd2hlcmUgd2UgaGF2ZSB0d28gYmFsbHMuIFN1cHBvc2Ugd2UgZHJvcCB0aGUgZmlyc3QgYmFsbCBmcm9tIGZsb29yIG4uIElmIGl0IGJyZWFrcyB3ZSYjMzk7cmUgaW4gdGhlIGNhc2Ugd2hlcmUgd2UgaGF2ZSBvbmUgYmFsbCByZW1haW5pbmcgYW5kIHdlIG5lZWQgdG8gZHJvcCBmcm9tIGZsb29ycyAxIHRvIG4tMSBpbiBzZXF1ZW5jZSwgeWllbGRpbmcgbiBkcm9wcyBpbiB0aGUgd29yc3QgY2FzZSAodGhlIGZpcnN0IGJhbGwgaXMgZHJvcHBlZCBvbmNlLCB0aGUgc2Vjb25kIGF0IG1vc3Qgbi0xIHRpbWVzKS4gSG93ZXZlciwgaWYgaXQgZG9lcyBub3QgYnJlYWsgd2hlbiBkcm9wcGVkIGZyb20gZmxvb3Igbiwgd2UgaGF2ZSByZWR1Y2VkIHRoZSBwcm9ibGVtIHRvIGRyb3BwaW5nIGZyb20gZmxvb3JzIG4rMSB0byAxMDAuIEluIGVpdGhlciBjYXNlIHdlIG11c3Qga2VlcCBpbiBtaW5kIHRoYXQgd2UmIzM5O3ZlIGFscmVhZHkgdXNlZCBvbmUgZHJvcC4gU28gdGhlIG1pbmltdW0gbnVtYmVyIG9mIGRyb3BzLCBpbiB0aGUgd29yc3QgY2FzZSwgaXMgdGhlIG1pbmltdW0gb3ZlciBhbGwgbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRvIGRldGVybWluZSB0aGUgbWluaW11bSBudW1iZXIgb2YgZHJvcHMgcmVxdWlyZWQsIGluIHRoZSB3b3JzdCBjYXNlLCBnaXZlbiBCIGJhbGxzIGFuZCBhbiBNLXN0b3J5IGJ1aWxkaW5nLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBQLCAoMSAmbGU7IFAgJmxlOyAxMDAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRocmVlICgzKSBkZWNpbWFsIGludGVnZXIgdmFsdWVzOiB0aGUgcHJvYmxlbSBudW1iZXIsIGZvbGxvd2VkIGJ5IGEgc3BhY2UsIGZvbGxvd2VkIGJ5IHRoZSBudW1iZXIgb2YgYmFsbHMgQiwgKDEgJmxlOyBCICZsZTsgNTApLCBmb2xsb3dlZCBieSBhIHNwYWNlIGFuZCB0aGUgbnVtYmVyIG9mIGZsb29ycyBpbiB0aGUgYnVpbGRpbmcgTSwgKDEgJmxlOyBNICZsZTsgMTAwMCkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIGdlbmVyYXRlIG9uZSBsaW5lIG9mIG91dHB1dCB3aXRoIHRoZSBmb2xsb3dpbmcgdmFsdWVzOiBUaGUgZGF0YSBzZXQgbnVtYmVyIGFzIGEgZGVjaW1hbCBpbnRlZ2VyLCBhIHNwYWNlLCBhbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGRyb3BzIG5lZWRlZCBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgdmFsdWVzIG9mIEIgYW5kIE0uJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d