시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 117 | 73 | 46 | 79.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을 넘지 않는다.
첫째 줄에 루트에서 입력으로 주어진 기약분수까지 가는 경로를 출력한다.
2/5
LRR
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 B번