시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB181271458439.540%

문제

다음과 같은 귀납적인 규칙에 의해서 만들어지는 무한한 크기의 이진 트리를 생각하자. 각각의 노드에는 두 정수의 순서쌍이 할당되어 있다.

  1. 루트에는 (1, 1)이 할당된다.
  2. 어떤 노드가 (a, b)가 할당되었을 때, 그 노드의 왼쪽 자식에는 (a+b, b)가 할당되고, 오른쪽 자식에는 (a, a+b)가 할당된다.

우리는 어떤 노드가 주어졌을 때, 루트에서 그 노드로 이동하는 최단 경로를 찾으려 한다. 하지만 최단 경로가 매우 길 수도 있기 때문에, 왼쪽 자식으로 이동하는 회수와 오른쪽 자식으로 이동하는 회수를 찾으려고 한다.

입력으로 두 정수 A, B가 주어졌을 때, 루트에서 (A, B)가 할당된 노드까지 최단 경로로 이동할 때, 왼쪽 자식으로 이동하는 회수와 오른쪽 자식으로 이동하는 회수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다.

출력

첫째 줄에 두 정수 L, R을 출력한다. 각각은 왼쪽으로 이동한 회수, 오른쪽으로 이동한 회수를 나타낸다.

예제 입력 1

3 4

예제 출력 1

2 1
W3sicHJvYmxlbV9pZCI6IjIwNzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWQ1NWNcdWM3NzRcdWM5YzRcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGMwXHViMGE5XHVjODAxXHVjNzc4IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWM3NThcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOWMwXHViMjk0IFx1YmIzNFx1ZDU1Y1x1ZDU1YyBcdWQwNmNcdWFlMzBcdWM3NTggXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWM3OTAuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIxNzhcdWI0ZGNcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWMzMGRcdWM3NzQgXHVkNTYwXHViMmY5XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWI4ZThcdWQyYjhcdWM1ZDBcdWIyOTQgKDEsIDEpXHVjNzc0IFx1ZDU2MFx1YjJmOVx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNWI0XHViNWE0IFx1YjE3OFx1YjRkY1x1YWMwMCAoYSwgYilcdWFjMDAgXHVkNTYwXHViMmY5XHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNWQwXHViMjk0IChhK2IsIGIpXHVhYzAwIFx1ZDU2MFx1YjJmOVx1YjQxOFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YzJkZFx1YzVkMFx1YjI5NCAoYSwgYStiKVx1YWMwMCBcdWQ1NjBcdWIyZjlcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1YzViNFx1YjVhNCBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YWRmOCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjYzNlXHVjNzNjXHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWFjMDAgXHViOWU0XHVjNmIwIFx1YWUzOCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVkNjhjXHVjMjE4XHVjNjQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViNDUwIFx1YzgxNVx1YzIxOCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyAoQSwgQilcdWFjMDAgXHVkNTYwXHViMmY5XHViNDFjIFx1YjE3OFx1YjRkY1x1YWU0Y1x1YzljMCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGMsIFx1YzY3Y1x1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1ZDY4Y1x1YzIxOFx1YzY0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWQ2OGNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggQSwgQigxICZsZTsgQSwgQiAmbGU7IDIsMDAwLDAwMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzk4XHViYWJiXHViNDFjIFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTCwgUlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc0MCBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjIFx1ZDY4Y1x1YzIxOCwgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWQ2OGNcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIwNzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCaW5hcnkgVHJlZSIsImRlc2NyaXB0aW9uIjoiPHA+QmluYXJ5IHRyZWVzIGFyZSBhIGNvbW1vbiBkYXRhIHN0cnVjdHVyZSBpbiBjb21wdXRlciBzY2llbmNlLiBJbiB0aGlzIHByb2JsZW0gd2Ugd2lsbCBsb29rIGF0IGFuIGluZmluaXRlIGJpbmFyeSB0cmVlIHdoZXJlIHRoZSBub2RlcyBjb250YWluIGEgcGFpciBvZiBpbnRlZ2Vycy4gVGhlIHRyZWUgaXMgY29uc3RydWN0ZWQgbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSByb290IGNvbnRhaW5zIHRoZSBwYWlyICgxLCAxKS48XC9saT5cclxuXHQ8bGk+SWYgYSBub2RlIGNvbnRhaW5zIChhLCBiKSB0aGVuIGl0cyBsZWZ0IGNoaWxkIGNvbnRhaW5zIChhICsgYiwgYikgYW5kIGl0cyByaWdodCBjaGlsZCAoYSwgYSArIGIpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGNvbnRlbnRzIChhLCBiKSBvZiBzb21lIG5vZGUgb2YgdGhlIGJpbmFyeSB0cmVlIGRlc2NyaWJlZCBhYm92ZSwgc3VwcG9zZSB5b3UgYXJlIHdhbGtpbmcgZnJvbSB0aGUgcm9vdCBvZiB0aGUgdHJlZSB0byB0aGUgZ2l2ZW4gbm9kZSBhbG9uZyB0aGUgc2hvcnRlc3QgcG9zc2libGUgcGF0aC4gQ2FuIHlvdSBmaW5kIG91dCBob3cgb2Z0ZW4geW91IGhhdmUgdG8gZ28gdG8gYSBsZWZ0IGNoaWxkIGFuZCBob3cgb2Z0ZW4gdG8gYSByaWdodCBjaGlsZD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIGkgYW5kIGogKDEgJmxlOyBpLCBqICZsZTsgMiZtaWRkb3Q7MTA8c3VwPjk8XC9zdXA+KSB0aGF0IHJlcHJlc2VudCBhIG5vZGUgKGksIGopLiBZb3UgY2FuIGFzc3VtZSB0aGF0IHRoaXMgaXMgYSB2YWxpZCBub2RlIGluIHRoZSBiaW5hcnkgdHJlZSBkZXNjcmliZWQgYWJvdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHR3byBudW1iZXJzIGwgYW5kIHIgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLCB3aGVyZSBsIGlzIGhvdyBvZnRlbiB5b3UgaGF2ZSB0byBnbyBsZWZ0IGFuZCByIGlzIGhvdyBvZnRlbiB5b3UgaGF2ZSB0byBnbyByaWdodCB3aGVuIHRyYXZlcnNpbmcgdGhlIHRyZWUgZnJvbSB0aGUgcm9vdCB0byB0aGUgbm9kZSBnaXZlbiBpbiB0aGUgaW5wdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2005 (Single) 4번

  • 데이터를 추가한 사람: jjwdi0