무한 이진 트리
면접 대비시간 제한1초메모리 제한128 MB
덧셈 규칙으로 정의된 무한 이진 트리에서 (A,B)에 도달하기 위한 왼쪽 이동과 오른쪽 이동 횟수를 유클리드 알고리즘처럼 역추적해서 구합니다.
문제
다음 규칙으로 만들어지는 무한한 이진 트리를 생각하자. 각 노드에는 두 정수의 순서쌍이 적혀 있다.
- 루트에는 (1, 1)이 적혀 있다.
- 어떤 노드에 (a, b)가 적혀 있으면, 그 노드의 왼쪽 자식에는 (a+b, b)가 적히고 오른쪽 자식에는 (a, a+b)가 적힌다.
어떤 노드가 주어졌을 때 루트에서 그 노드까지 가는 최단 경로를 찾고 싶다. 경로 자체는 매우 길 수 있으므로, 왼쪽 자식으로 이동한 횟수와 오른쪽 자식으로 이동한 횟수만 구한다.
두 정수 A, B가 주어질 때, 루트에서 (A, B)가 적힌 노드까지 최단 경로로 이동하면서 왼쪽 자식으로 이동한 횟수와 오른쪽 자식으로 이동한 횟수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 A, B가 주어진다. (1 ≤ A, B ≤ 2,000,000,000)
잘못된 입력은 주어지지 않는다.
출력
첫째 줄에 두 정수 L, R을 출력한다. L은 왼쪽 자식으로 이동한 횟수, R은 오른쪽 자식으로 이동한 횟수이다.