문제
아래와 같이 생성된 분수 수열에 번호를 붙인 무한한 포화이진트리를 생각해보자.
* 루트는 1/1 이다. * p/q 의 왼쪽 자식은 p/(p+q) 이다. * p/q 의 오른쪽 자식은 (p+q)/q 이다.
이 트리의 일부 모습은 아래와 같다.
이 트리의 방문 순서는 너비우선탐색이다. 따라서 트리의 k번째 값을 F(k)라고 할 때, 값들을 나열하면 F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F[5] = 3/2, F[6] = 2/3 .... 이 된다.
분수 수열 F(n) = p/q, 가 주어질 때, F(n+1)을 구하는 프로그램을 작성하시오.
입력
첫 행에 테스트케이스의 수 T (1 ≤ T ≤ 100)가 입력된다.
이어 T개의 행에 각각의 데이터가 입력된다.
각 데이터의 첫 수는 테스트케이스 번호이다.
다음으로 p/q가 입력된다.(0 ≤ p, q ≤ 2,147,483,647)
출력
각 테스트케이스에 대하여 테스트케이스번호, F(n+1)의 값을 a/b꼴로 출력한다.
예제
5
1 1/1
2 1/3
3 5/2
4 2178309/1346269
5 1/1500
1 1/2
2 3/2
3 2/5
4 1346269/1860498
5 1500/9999999
출처
Greater New York 2014
로그인해야 코드를 작성할 수 있어요.