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

문제

새트리는 무한 이진 트리이고, 첫 5레벨은 다음과 같이 생겼다.

새트리의 각 노드는 다음과 같이 재귀적으로 정의할 수 있다.

여기서 bird는 완전 트리를 의미하고, bird+1은 트리의 모든 분수에 1를 더하는 것을 의미하고, 1/bird는 트리의 모든 분수를 뒤집는 것을 의미한다.

놀랍게도 트리에는 모든 유리수가 딱 한 번씩 등장한다. 따라서, 모든 기약분수는 유일한 경로가 있다. 경로는 왼쪽 자식노드로 갈 때는 L, 오른쪽으로 갈 때는 R로 표현한다. 예를 들어, 2/5는 LRR로 표현할 수 있다.

기약분수가 주어졌을 때, 루트에서 그 노드까지의 경로를 L과 R로 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 a와 b가 '/'로 구분되어 주어진다. a는 기약분수의 분자, b는 분모이며, a와 b가 동시에 1인 경우는 없다. 또한, gcd(a,b) = 1을 만족한다. (1 ≤ a,b ≤ 109) 경로의 길이는 10,000을 넘지 않는다.

출력

첫째 줄에 루트에서 입력으로 주어진 기약분수까지 가는 경로를 출력한다. 

예제 입력 1

2/5

예제 출력 1

LRR
W3sicHJvYmxlbV9pZCI6IjM2NTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzhcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjOFx1ZDJiOFx1YjlhY1x1YjI5NCBcdWJiMzRcdWQ1NWMgXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YWNlMCwgXHVjY2FiIDVcdWI4MDhcdWJjYThcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFjYmNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYnQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjQwcHg7IHdpZHRoOjU2NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzBjOFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMDEgXHViMTc4XHViNGRjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjN2FjXHVhZGMwXHVjODAxXHVjNzNjXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjI0N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzExYyBiaXJkXHViMjk0IFx1YzY0NFx1YzgwNCBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwLCBiaXJkKzFcdWM3NDAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJkODRcdWMyMThcdWM1ZDAgMVx1Yjk3YyBcdWIzNTRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YWNlMCwgMVwvYmlyZFx1YjI5NCBcdWQyYjhcdWI5YWNcdWM3NTggXHViYWE4XHViNGUwIFx1YmQ4NFx1YzIxOFx1Yjk3YyBcdWI0YTRcdWM5ZDFcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTgwXHViNzhkXHVhYzhjXHViM2M0IFx1ZDJiOFx1YjlhY1x1YzVkMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNzIwXHViOWFjXHVjMjE4XHVhYzAwIFx1YjUzMSBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWJhYThcdWI0ZTAgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1YjE3OFx1YjRkY1x1Yjg1YyBcdWFjMDggXHViNTRjXHViMjk0IEwsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDggXHViNTRjXHViMjk0IFJcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyXC81XHViMjk0IExSUlx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWFkZjggXHViMTc4XHViNGRjXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBMXHVhY2ZjIFJcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIGFcdWM2NDAgYlx1YWMwMCAmIzM5O1wvJiMzOTtcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gYVx1YjI5NCBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWM3NTggXHViZDg0XHVjNzkwLCBiXHViMjk0IFx1YmQ4NFx1YmFhOFx1Yzc3NFx1YmE3MCwgYVx1YzY0MCBiXHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCAxXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YjYxMFx1ZDU1YywgZ2NkKGEsYikgPSAxXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC4gKDEgJmxlOyBhLGIgJmxlOyAxMDxzdXA+OTxcL3N1cD4pJm5ic3A7XHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMCwwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1YWU0Y1x1YzljMCBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNjUyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmlyZCB0cmVlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgQmlyZCB0cmVlIGlzIGFuIGluZmluaXRlIGJpbmFyeSB0cmVlLCB3aG9zZSBcdWZiMDFyc3QgNSBsZXZlbHMgbG9vayBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2J0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI0MHB4OyB3aWR0aDo1NjRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5JdCBjYW4gYmUgZGVmaW5lZCBhcyBmb2xsb3dzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojg1cHg7IHdpZHRoOjI0N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoaXMgaXMgYSBjby1yZWN1cnNpdmUgZGVmaW5pdGlvbiBpbiB3aGljaCBib3RoIG9jY3VycmVuY2VzIG9mIGJpcmQgcmVmZXIgdG8gdGhlIGZ1bGwgKGluZmluaXRlKSB0cmVlLjxcL3A+XHJcblxyXG48cD5UaGUgZXhwcmVzc2lvbiBiaXJkICsgMSBtZWFucyB0aGF0IDEgaXMgYWRkZWQgdG8gZXZlcnkgZnJhY3Rpb24gaW4gdGhlIHRyZWUsIGFuZCAxXC9iaXJkIG1lYW5zIHRoYXQgZXZlcnkgZnJhY3Rpb24gaW4gdGhlIHRyZWUgaXMgaW52ZXJ0ZWQgKHNvIGFcL2IgYmVjb21lcyBiXC9hKS48XC9wPlxyXG5cclxuPHA+U3VycHJpc2luZ2x5LCB0aGUgdHJlZSBjb250YWlucyBldmVyeSBwb3NpdGl2ZSByYXRpb25hbCBudW1iZXIgZXhhY3RseSBvbmNlLCBzbyBldmVyeSByZWR1Y2VkIGZyYWN0aW9uIGlzIGF0IGEgdW5pcXVlIHBsYWNlIGluIHRoZSB0cmVlLiBIZW5jZSwgd2UgY2FuIGFsc28gZGVzY3JpYmUgYSByYXRpb25hbCBudW1iZXIgYnkgZ2l2aW5nIGRpcmVjdGlvbnMgKEwgZm9yIGxlZnQgc3VidHJlZSwgUiBmb3IgcmlnaHQgc3VidHJlZSkgaW4gdGhlIEJpcmQgdHJlZS4gRm9yIGV4YW1wbGUsIDJcLzUgaXMgcmVwcmVzZW50ZWQgYnkgTFJSLiBHaXZlbiBhIHJlZHVjZWQgZnJhY3Rpb24sIHJldHVybiBhIHN0cmluZyBjb25zaXN0aW5nIG9mIEwmcnNxdW87cyBhbmQgUiZyc3F1bztzOiB0aGUgZGlyZWN0aW9ucyB0byBsb2NhdGUgdGhpcyBmcmFjdGlvbiBmcm9tIHRoZSB0b3Agb2YgdGhlIHRyZWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxICZsZTsmbmJzcDthLCZuYnNwO2IgJmxlOyZuYnNwOzEwPHN1cD45PFwvc3VwPiksIHNlcGFyYXRlZCBieSBhICZyc3F1bztcLyZyc3F1bzsuIFRoZXNlIHJlcHJlc2VudCB0aGUgbnVtZXJhdG9yIGFuZCBkZW5vbWluYXRvciBvZiBhIHJlZHVjZWQgZnJhY3Rpb24uIFRoZSBpbnRlZ2VycyBhIGFuZCBiIGFyZSBub3QgYm90aCBlcXVhbCB0byAxLCBhbmQgdGhleSBzYXRpc2Z5IGdjZChhLCBiKSA9IDEuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGV2ZXJ5IHRlc3QgY2FzZSB0aGUgbGVuZ3RoIG9mIHRoZSBzdHJpbmcgd2l0aCBkaXJlY3Rpb25zIHdpbGwgYmUgYXQgbW9zdCAxMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHRoZSBzdHJpbmcgcmVwcmVzZW50YXRpb24gb2YgdGhlIGxvY2F0aW9uIG9mIHRoaXMgZnJhY3Rpb24gaW4gdGhlIEJpcmQgdHJlZS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 B번