시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 100 19 15 35.714%

문제

콜라츠 추측은 흥미로운 현상이다. 이 법칙은 간단해보이지만, 수학적으로 아직까지 증명되어있지 않은 문제이다. 우리는 이 추측이 옳다고 받아들이겠다.

콜라츠 추측을 설명하면 다음과 같다. 우선 다음과 같은 양의 정수 수열 xi 를 생각하자.

  • 만약 xi 가 짝수이면, xi+1=xi/2
  • 만약 xi 가 홀수이면, xi+1=3*xi +1 이다.
콜라츠 추측은 이렇게 만든 수열은 결국 1이 된다는 것이다.
과학자들은, 컴퓨터를 이용하여 첫번째 수열이 258 보다 작으면, 이 추측은 참이라고 증명했다.

이제 문제를 보자.

두개의 양의 정수를 준다. 각각의 수에 대해서 콜라츠 추측으로 만든 수열을 생각하자.

각각의 수열을 비교하였을때 처음으로 같은 숫자가 나왔을때 , 각각 몇번째 수열에서 만나는지 구해본다. 문제의 편의를 위해, 이 수열은 1이 나오면 더이상 진행하지 않는다고 하자. ( 1 다음에 나올 수열을 생각하면, 1, 4, 2, 1, 4, 2, 1로 반복되기 때문이다.)

입력

입력은 몇개의 테스트 케이스로 구성된다. 각 테스트 케이스는 두개의 정수 A와 B가 주어진다. ( 1 ≤ A, B ≤ 1,000,000) 마지막 줄은 두개의 0으로 구성된다.

출력

각각의 테스트 케이스마다 다음과 같은 문장을 한줄에 출력한다.

"A needs SA steps, B needs SB steps, they meet at C"

SA와 SB는 A와 B로 수열을 만들고, 처음으로 같은 숫자 C가 나왔을때 각각의 수열에서 몇번째 인지 알려주는 숫자이다.

예제 입력 1

7 8
27 30
0 0

예제 출력 1

7 needs 13 steps, 8 needs 0 steps, they meet at 8
27 needs 95 steps, 30 needs 2 steps, they meet at 46
W3sicHJvYmxlbV9pZCI6IjY2MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNWNcdWI3N2NcdWNlMjAgXHVjZDk0XHVjZTIxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNmNWNcdWI3N2NcdWNlMjAgXHVjZDk0XHVjZTIxXHVjNzQwIFx1ZDc2NVx1YmJmOFx1Yjg1Y1x1YzZiNCBcdWQ2MDRcdWMwYzFcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJjOTVcdWNlNTlcdWM3NDAgXHVhYzA0XHViMmU4XHVkNTc0XHViY2Y0XHVjNzc0XHVjOWMwXHViOWNjLCBcdWMyMThcdWQ1NTlcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNTQ0XHVjOWMxXHVhZTRjXHVjOWMwIFx1Yzk5ZFx1YmE4NVx1YjQxOFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgXHViYjM4XHVjODFjXHVjNzc0XHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0IFx1Y2Q5NFx1Y2UyMVx1Yzc3NCBcdWM2MzNcdWIyZTRcdWFjZTAgXHViYzFiXHVjNTQ0XHViNGU0XHVjNzc0XHVhY2EwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNmNWNcdWI3N2NcdWNlMjAgXHVjZDk0XHVjZTIxXHVjNzQ0IFx1YzEyNFx1YmE4NVx1ZDU1OFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWM2YjBcdWMxMjAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IFx1YzIxOFx1YzVmNCB4PHN1Yj5pIDxcL3N1Yj5cdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCB4PHN1Yj5pPFwvc3ViPiBcdWFjMDAgXHVjOWRkXHVjMjE4XHVjNzc0XHViYTc0LCB4PHN1Yj5pKzE8XC9zdWI+PXg8c3ViPmk8XC9zdWI+XC8yPFwvbGk+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCB4PHN1Yj5pPFwvc3ViPiBcdWFjMDAgXHVkNjQwXHVjMjE4XHVjNzc0XHViYTc0LCB4PHN1Yj5pKzE8XC9zdWI+PTMqeDxzdWI+aSA8XC9zdWI+KzEgXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxkaXY+XHVjZjVjXHViNzdjXHVjZTIwIFx1Y2Q5NFx1Y2UyMVx1Yzc0MCBcdWM3NzRcdWI4MDdcdWFjOGMgXHViOWNjXHViNGUwIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWFjYjBcdWFkNmQgMVx1Yzc3NCBcdWI0MWNcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL2Rpdj5cclxuXHJcbjxkaXY+XHVhY2ZjXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwLCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWMyMThcdWM1ZjRcdWM3NzQgMjxzdXA+NTg8XC9zdXA+IFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3M2NcdWJhNzQsIFx1Yzc3NCBcdWNkOTRcdWNlMjFcdWM3NDAgXHVjYzM4XHVjNzc0XHViNzdjXHVhY2UwIFx1Yzk5ZFx1YmE4NVx1ZDU4OFx1YjJlNC48XC9kaXY+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMgXHViYjM4XHVjODFjXHViOTdjIFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHViNDUwXHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjOTAwXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWNmNWNcdWI3N2NcdWNlMjAgXHVjZDk0XHVjZTIxXHVjNzNjXHViODVjIFx1YjljY1x1YjRlMCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YmU0NFx1YWQ1MFx1ZDU1OFx1YzYwMFx1Yzc0NFx1YjU0YyBcdWNjOThcdWM3NGNcdWM3M2NcdWI4NWMgXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWIwOThcdWM2NTRcdWM3NDRcdWI1NGMgLCBcdWFjMDFcdWFjMDEgXHViYTg3XHViYzg4XHVjOWY4IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTc0XHViY2Y4XHViMmU0LiBcdWJiMzhcdWM4MWNcdWM3NTggXHVkM2I4XHVjNzU4XHViOTdjIFx1YzcwNFx1ZDU3NCwgXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0MCAxXHVjNzc0IFx1YjA5OFx1YzYyNFx1YmE3NCBcdWIzNTRcdWM3NzRcdWMwYzEgXHVjOWM0XHVkNTg5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuICggMSBcdWIyZTRcdWM3NGNcdWM1ZDAgXHViMDk4XHVjNjJjIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWMwZGRcdWFjMDFcdWQ1NThcdWJhNzQsIDEsIDQsIDIsIDEsIDQsIDIsIDFcdWI4NWMgXHViYzE4XHViY2Y1XHViNDE4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxvbD5cclxuPFwvb2w+IiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHViYTg3XHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICggMSAmbGU7IEEsIEIgJmxlOyAxLDAwMCwwMDApIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDAgXHViNDUwXHVhYzFjXHVjNzU4IDBcdWM3M2NcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYjM4XHVjN2E1XHVjNzQ0IFx1ZDU1Y1x1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiZxdW90O0EgbmVlZHMgUzxzdWI+QTxcL3N1Yj4gc3RlcHMsIEIgbmVlZHMgUzxzdWI+QjxcL3N1Yj4gc3RlcHMsIHRoZXkgbWVldCBhdCBDJnF1b3Q7PFwvcD5cclxuXHJcbjxwPlM8c3ViPkE8XC9zdWI+XHVjNjQwIFM8c3ViPkI8XC9zdWI+XHViMjk0IEFcdWM2NDAgQlx1Yjg1YyBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0XHVhY2UwLCBcdWNjOThcdWM3NGNcdWM3M2NcdWI4NWMgXHVhYzE5XHVjNzQwIFx1YzIyYlx1Yzc5MCBDXHVhYzAwIFx1YjA5OFx1YzY1NFx1Yzc0NFx1YjU0YyBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YmE4N1x1YmM4OFx1YzlmOCBcdWM3NzhcdWM5YzAgXHVjNTRjXHViODI0XHVjOGZjXHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NjE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29sbGF0eiBDb25qZWN0dXJlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgQ29sbGF0eiBDb25qZWN0dXJlIGlzIGFuIGludGVyZXN0aW5nIHBoZW5vbWVub24uIFRob3VnaCBpdHMgcHJpbmNpcGxlIGlzIHZlcnkgc2ltcGxlLCBpdCBzdGlsbCByZW1haW5zIGFtb25nIHVucmVzb2x2ZWQgcHJvYmxlbXMgaW4gbWF0aGVtYXRpY3MsIGV2ZW4gYWZ0ZXIgbWFueSB5ZWFycyBvZiBzdHVkeS4gSG93ZXZlciwgdGhlIHllYXJzIG9mIGludGVuc2l2ZSByZXNlYXJjaCBicm91Z2h0IGF0IGxlYXN0IHNvbWUgcmVzdWx0cywgd2hpY2ggaXMgYSBodWdlIGFkdmFudGFnZSBvZiB0aGUgaHVtYW4gcmFjZSBhZ2FpbnN0IHRoZSBhbGllbnMsIGJlY2F1c2UgdGhleSBkaWQgbm90IHN0dWR5IHRoZSBjb25qZWN0dXJlIGZvciBzbyBtYW55IHllYXJzLiBXZSB3YW50IHRvIGtlZXAgdGhpcyBhZHZhbnRhZ2UuPFwvcD5cclxuXHJcbjxwPkltYWdpbmUgYSBzZXF1ZW5jZSBkZWZpbmVkIHJlY3Vyc2l2ZWx5IGFzIGZvbGxvd3M6IFN0YXJ0IHdpdGggYW55IHBvc2l0aXZlIGludGVnZXIgeDxzdWI+MDxcL3N1Yj4gKHNvLWNhbGxlZCAmcmRxdW87c3RhcnRpbmcgdmFsdWUmcmRxdW87KS4gVGhlbiByZXBlYXQgdGhlIGZvbGxvd2luZzo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5pZiB4PHN1Yj5pPFwvc3ViPiBpcyBldmVuLCB0aGVuIHg8c3ViPmkrMTxcL3N1Yj4gPSB4PHN1Yj5pPFwvc3ViPlwvMiAoJnJkcXVvO2hhbGYgLi4uJnJkcXVvOyk8XC9saT5cclxuXHQ8bGk+aWYgeDxzdWI+aTxcL3N1Yj4gaXMgb2RkLCB0aGVuIHg8c3ViPmkrMTxcL3N1Yj4gPSAzeDxzdWI+aTxcL3N1Yj4gKyAxICgmcmRxdW87Li4uIG9yIHRyaXBsZSBwbHVzIG9uZSZyZHF1bzspPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIENvbGxhdHogQ29uamVjdHVyZSBzYXlzIHRoYXQgZXZlcnkgc3VjaCBzZXF1ZW5jZSB3aWxsIGV2ZW50dWFsbHkgcmVhY2ggMS4gSXQgaGFzIHN0aWxsIG5vdCBiZWVuIHByb3ZlbiB1bnRpbCB0b2RheSBidXQgd2UgYWxyZWFkeSBrbm93IGZvciBzdXJlIHRoYXQgdGhpcyBpcyB0cnVlIGZvciBldmVyeSB4PHN1Yj4wPFwvc3ViPiAmbHQ7IDI8c3VwPjU4PFwvc3VwPi4gKE5ldmVyIHRlbGwgdGhpcyB0byBhbGllbnMhKTxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHlvdSBhcmUgZ2l2ZW4gdHdvIHN0YXJ0aW5nIHZhbHVlcyBhbmQgeW91ciB0YXNrIGlzIHRvIHNheSBhZnRlciBob3cgbWFueSBzdGVwcyB0aGVpciBzZXF1ZW5jZXMgJmxkcXVvO21lZXQmcmRxdW87IGZvciB0aGUgZmlyc3QgdGltZSAod2hpY2ggbWVhbnMgdGhlIGZpcnN0IG51bWJlciB0aGF0IG9jY3VycyBpbiBib3RoIHNlcXVlbmNlcykgYW5kIGF0IHdoaWNoIG51bWJlciBpcyBpdCBnb2luZyB0byBoYXBwZW4uIEZvciBzaW1wbGljaXR5LCB3ZSB3aWxsIGFzc3VtZSB0aGF0IHRoZSBzZXF1ZW5jZSBkb2VzIG5vdCBjb250aW51ZSBvbmNlIGl0IGhhcyByZWFjaGVkIHRoZSBudW1iZXIgb25lLiBJbiByZWFsaXR5LCBpdCB3b3VsZCB0aGVuIHR1cm4gaW50byAxLCA0LCAyLCAxLCA0LCAyLCAxLC4gLi4sIHdoaWNoIHF1aWNrbHkgYmVjb21lcyBib3JpbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBpcyBkZXNjcmliZWQgYnkgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHR3byBpbnRlZ2VyIG51bWJlcnMgQSBhbmQgQiwgMSAmbGU7IEEsQiAmbGU7IDEgMDAwIDAwMC48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgc2VudGVuY2UgJmxkcXVvO0EgbmVlZHMgUzxzdWI+QTxcL3N1Yj4gc3RlcHMsIEIgbmVlZHMgUzxzdWI+QjxcL3N1Yj4gc3RlcHMsIHRoZXkgbWVldCBhdCBDJnJkcXVvOywgd2hlcmUgUzxzdWI+QTxcL3N1Yj4gYW5kIFM8c3ViPkI8XC9zdWI+IGFyZSB0aGUgbnVtYmVyIG9mIHN0ZXBzIG5lZWRlZCBpbiBib3RoIHNlcXVlbmNlcyB0byByZWFjaCB0aGUgc2FtZSBudW1iZXIgQy4gRm9sbG93IHRoZSBvdXRwdXQgZm9ybWF0IHByZWNpc2VseS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=