시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 27 18 13 72.222%

문제

각 노드의 값이 유리수인 완전 이진 트리를 생각해보자. 유리수 트리의 루트 노드는 1/1 이고, 노드 p/q 의 왼쪽 자식과 오른쪽 자식은 각각 p/(p+q)와 (p+q)/q를 가지며, 이러한 계산 방식으로 트리는 무한히 확장될 수 있다. 아래는 유리수 트리의 예시이다.

         1/1
    ______|______
    |            |
   1/2          2/1
 ___|___      ___|___
 |      |     |      |
1/3    3/2   2/3    3/1
...

유리수 트리에는 모든 양의 유리수가 한 번씩만 나타난다고 알려져 있고, 유리수 트리를 레벨 순회하면 다음과 같은 배열의 결과를 얻게 된다: 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...

유리수 트리가 주어졌을 때, 아래 두 개의 질문에 답해보시오:

  1. n 번째 배열 원소의 값은 무엇인가? (단, n >= 1) 예를 들어, 입력값이 2 라면 (즉, n=2), 정확한 출력값은 1/2 이 되어야 한다.
  2. p/q 가 입력으로 주어졌을 때, 해당 입력 값이 배열에서 몇 번째 원소인가? 예를 들어, 입력값이 1/2 라면, 출력값은 2가 되어야 한다.

입력

입력의 첫 번째 줄은 테스트 케이스의 개수 T 를 나타내고, 개별 테스트 케이스에 대한 내용이 뒤따라 나온다.

각 테스트 케이스는 한 줄로 이루어지면 다음과 같은 내용을 포함한다: 문제 ID (1 또는 2) + 1개(또는 2개)의 정수

  1. 문제 ID가 1인 경우, 한 개의 정수 n이 추가로 주어지며 배열에서 n번째에 위치한 값을 찾는다.
  2. 문제 ID가 2인 경우, 두 개의 정수 p, q가 추가로 주어지며 배열에서 p/q 값이 몇 번째에 위치하는지 찾는다.

조건

  • 1 <= T <= 100; p, q는 서로소이다.
  • 1 <= n, p, q <= 2^16 - 1; p/q 트리에서 16 보다 작거나 같은 레벨에 존재하는 값이다.

출력

개별 테스트 케이스에 대해:

  1. 문제 ID가 1인 경우, "Case #x : p q"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호 (1에서 시작)이고 p, q는 요청 된 배열 요소의 분자와 분모이다.
  2. 문제 ID가 2인 경우, "Case #x : n"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호 (1에서 시작)이고 n은 주어진 숫자의 배열내의 위치이다.

예제 입력

4
1 2
2 1 2
1 5
2 3 2

예제 출력

Case #1: 1 2
Case #2: 2
Case #3: 3 2
Case #4: 5

힌트