시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhY2ZjXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwLCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjE4XHVjNWY0XHVjNzc0IDI8c3VwPjU4PFwvc3VwPiBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzNjXHViYTc0LCBcdWM3NzQgXHVjZDk0XHVjZTIxXHVjNzQwIFx1Y2MzOFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWM5OWRcdWJhODVcdWQ1ODhcdWIyZTQuPFwvZGl2PlxyXG5cclxuPHA+XHVjNzc0XHVjODFjIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1YzkwMFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjZjVjXHViNzdjXHVjZTIwIFx1Y2Q5NFx1Y2UyMVx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWJlNDRcdWFkNTBcdWQ1NThcdWM2MDBcdWM3NDRcdWI1NGMgXHVjYzk4XHVjNzRjXHVjNzNjXHViODVjIFx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViMDk4XHVjNjU0XHVjNzQ0XHViNTRjICwgXHVhYzAxXHVhYzAxIFx1YmE4N1x1YmM4OFx1YzlmOCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViOWNjXHViMDk4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU3NFx1YmNmOFx1YjJlNC4gXHViYjM4XHVjODFjXHVjNzU4IFx1ZDNiOFx1Yzc1OFx1Yjk3YyBcdWM3MDRcdWQ1NzQsIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NDAgMVx1Yzc3NCBcdWIwOThcdWM2MjRcdWJhNzQgXHViMzU0XHVjNzc0XHVjMGMxIFx1YzljNFx1ZDU4OVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiAoIDEgXHViMmU0XHVjNzRjXHVjNWQwIFx1YjA5OFx1YzYyYyBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0LCAxLCA0LCAyLCAxLCA0LCAyLCAxXHViODVjIFx1YmMxOFx1YmNmNVx1YjQxOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuKTxcL3A+XHJcblxyXG48b2w+XHJcbjxcL29sPiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YmE4N1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoIDEgJmxlOyBBLCBCICZsZTsgMSwwMDAsMDAwKSBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwIFx1YjQ1MFx1YWMxY1x1Yzc1OCAwXHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmIzOFx1YzdhNVx1Yzc0NCBcdWQ1NWNcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4mcXVvdDtBIG5lZWRzIFM8c3ViPkE8XC9zdWI+IHN0ZXBzLCBCIG5lZWRzIFM8c3ViPkI8XC9zdWI+IHN0ZXBzLCB0aGV5IG1lZXQgYXQgQyZxdW90OzxcL3A+XHJcblxyXG48cD5TPHN1Yj5BPFwvc3ViPlx1YzY0MCBTPHN1Yj5CPFwvc3ViPlx1YjI5NCBBXHVjNjQwIEJcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCwgXHVjYzk4XHVjNzRjXHVjNzNjXHViODVjIFx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTAgQ1x1YWMwMCBcdWIwOThcdWM2NTRcdWM3NDRcdWI1NGMgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWJhODdcdWJjODhcdWM5ZjggXHVjNzc4XHVjOWMwIFx1YzU0Y1x1YjgyNFx1YzhmY1x1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjYxNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvbGxhdHogQ29uamVjdHVyZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIENvbGxhdHogQ29uamVjdHVyZSBpcyBhbiBpbnRlcmVzdGluZyBwaGVub21lbm9uLiBUaG91Z2ggaXRzIHByaW5jaXBsZSBpcyB2ZXJ5IHNpbXBsZSwgaXQgc3RpbGwgcmVtYWlucyBhbW9uZyB1bnJlc29sdmVkIHByb2JsZW1zIGluIG1hdGhlbWF0aWNzLCBldmVuIGFmdGVyIG1hbnkgeWVhcnMgb2Ygc3R1ZHkuIEhvd2V2ZXIsIHRoZSB5ZWFycyBvZiBpbnRlbnNpdmUgcmVzZWFyY2ggYnJvdWdodCBhdCBsZWFzdCBzb21lIHJlc3VsdHMsIHdoaWNoIGlzIGEgaHVnZSBhZHZhbnRhZ2Ugb2YgdGhlIGh1bWFuIHJhY2UgYWdhaW5zdCB0aGUgYWxpZW5zLCBiZWNhdXNlIHRoZXkgZGlkIG5vdCBzdHVkeSB0aGUgY29uamVjdHVyZSBmb3Igc28gbWFueSB5ZWFycy4gV2Ugd2FudCB0byBrZWVwIHRoaXMgYWR2YW50YWdlLjxcL3A+XHJcblxyXG48cD5JbWFnaW5lIGEgc2VxdWVuY2UgZGVmaW5lZCByZWN1cnNpdmVseSBhcyBmb2xsb3dzOiBTdGFydCB3aXRoIGFueSBwb3NpdGl2ZSBpbnRlZ2VyIHg8c3ViPjA8XC9zdWI+IChzby1jYWxsZWQgJnJkcXVvO3N0YXJ0aW5nIHZhbHVlJnJkcXVvOykuIFRoZW4gcmVwZWF0IHRoZSBmb2xsb3dpbmc6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+aWYgeDxzdWI+aTxcL3N1Yj4gaXMgZXZlbiwgdGhlbiB4PHN1Yj5pKzE8XC9zdWI+ID0geDxzdWI+aTxcL3N1Yj5cLzIgKCZyZHF1bztoYWxmIC4uLiZyZHF1bzspPFwvbGk+XHJcblx0PGxpPmlmIHg8c3ViPmk8XC9zdWI+IGlzIG9kZCwgdGhlbiB4PHN1Yj5pKzE8XC9zdWI+ID0gM3g8c3ViPmk8XC9zdWI+ICsgMSAoJnJkcXVvOy4uLiBvciB0cmlwbGUgcGx1cyBvbmUmcmRxdW87KTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBDb2xsYXR6IENvbmplY3R1cmUgc2F5cyB0aGF0IGV2ZXJ5IHN1Y2ggc2VxdWVuY2Ugd2lsbCBldmVudHVhbGx5IHJlYWNoIDEuIEl0IGhhcyBzdGlsbCBub3QgYmVlbiBwcm92ZW4gdW50aWwgdG9kYXkgYnV0IHdlIGFscmVhZHkga25vdyBmb3Igc3VyZSB0aGF0IHRoaXMgaXMgdHJ1ZSBmb3IgZXZlcnkgeDxzdWI+MDxcL3N1Yj4gJmx0OyAyPHN1cD41ODxcL3N1cD4uIChOZXZlciB0ZWxsIHRoaXMgdG8gYWxpZW5zISk8XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB5b3UgYXJlIGdpdmVuIHR3byBzdGFydGluZyB2YWx1ZXMgYW5kIHlvdXIgdGFzayBpcyB0byBzYXkgYWZ0ZXIgaG93IG1hbnkgc3RlcHMgdGhlaXIgc2VxdWVuY2VzICZsZHF1bzttZWV0JnJkcXVvOyBmb3IgdGhlIGZpcnN0IHRpbWUgKHdoaWNoIG1lYW5zIHRoZSBmaXJzdCBudW1iZXIgdGhhdCBvY2N1cnMgaW4gYm90aCBzZXF1ZW5jZXMpIGFuZCBhdCB3aGljaCBudW1iZXIgaXMgaXQgZ29pbmcgdG8gaGFwcGVuLiBGb3Igc2ltcGxpY2l0eSwgd2Ugd2lsbCBhc3N1bWUgdGhhdCB0aGUgc2VxdWVuY2UgZG9lcyBub3QgY29udGludWUgb25jZSBpdCBoYXMgcmVhY2hlZCB0aGUgbnVtYmVyIG9uZS4gSW4gcmVhbGl0eSwgaXQgd291bGQgdGhlbiB0dXJuIGludG8gMSwgNCwgMiwgMSwgNCwgMiwgMSwuIC4uLCB3aGljaCBxdWlja2x5IGJlY29tZXMgYm9yaW5nLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgZGVzY3JpYmVkIGJ5IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlciBudW1iZXJzIEEgYW5kIEIsIDEgJmxlOyBBLEIgJmxlOyAxIDAwMCAwMDAuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IHRlc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyB0d28gemVyb3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIHNlbnRlbmNlICZsZHF1bztBIG5lZWRzIFM8c3ViPkE8XC9zdWI+IHN0ZXBzLCBCIG5lZWRzIFM8c3ViPkI8XC9zdWI+IHN0ZXBzLCB0aGV5IG1lZXQgYXQgQyZyZHF1bzssIHdoZXJlIFM8c3ViPkE8XC9zdWI+IGFuZCBTPHN1Yj5CPFwvc3ViPiBhcmUgdGhlIG51bWJlciBvZiBzdGVwcyBuZWVkZWQgaW4gYm90aCBzZXF1ZW5jZXMgdG8gcmVhY2ggdGhlIHNhbWUgbnVtYmVyIEMuIEZvbGxvdyB0aGUgb3V0cHV0IGZvcm1hdCBwcmVjaXNlbHkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d