[ Google CT2004 ] RoundA : Problem B. Rational Number Tree

Problem: 
Consider an infinite complete binary tree where the root node is 1/1 and left and right childs of node p/q are p/(p+q) and (p+q)/q, respectively. This tree looks like: 
 

It is known that every positive rational number appears exactly once in this tree. A level-order traversal of the tree results in the following array: 

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...

Please solve the following two questions: 

1. Find the n-th element of the array, where n starts from 1. For example, for the input 2, the correct output is 1/2.
2. Given p/q, find its position in the array. As an example, the input 1/2 results in the output 2.

Input: 
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line. The line contains a problem id (1 or 2) and one or two additional integers: 

If the problem id is 1, then only one integer n is given, and you are expected to find the n-th element of the array.
If the problem id is 2, then two integers p and q are given, and you are expected to find the position of p/q in the array.

Output: 
For each test case: 

If the problem id is 1, then output one line containing "Case #x: p q", where x is the case number (starting from 1), and p, q are numerator and denominator of the asked array element, respectively.
If the problem id is 2, then output one line containing "Case #x: n", where x is the case number (starting from 1), and n is the position of the given number.

Limits: 
1 ≤ T ≤ 100; p and q are relatively prime. 

Small dataset 
1 ≤ n, p, q ≤ 216-1; p/q is an element in a tree with level number ≤ 16. 

Large dataset 
1 ≤ n, p, q ≤ 264-1; p/q is an element in a tree with level number ≤ 64. 

Sample: 

Input 
4
1 2
2 1 2
1 5
2 3 2

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

One Solution: 
針對第一個問題: 

1. Find the n-th element of the array, where n starts from 1. For example, for the input 2, the correct output is 1/2.

解問題的思維是當你能決定某個位置在 binary tree 走的路徑, 那接下來的運算就是簡單的加法. 假設父節點是 (p,q) 的話: 

- 往左邊是 (p,(p+q))
- 往右邊是 ((p+q),q)

所以接下來便是決定 n-th 在 binary tree 走的路徑. 接著我們把 n 轉成二進位對應到原先 binary tree: 
 

如此可以觀察到 0->往左邊; 1->往右邊 (紅色的數字可以忽略), 所以可以知道: 

n=4=100: 往左邊 > 往左邊
n=5=101: 往左邊 > 往右邊
n=6=110: 往右邊 > 往左邊
...

所以用來解問題一的類別設計如下: 

view plaincopy to clipboardprint?

1. public static class P1{  
2.     public long p=1;  
3.     public long q=1;  
4.       
5.     public void move(char c)  
6.     {  
7.         if(c=='0') q = p+q;           
8.         else p = p+q;             
9.     }  
10.       
11.     @Override  
12.     public String toString() {return String.format("%d %d", p,q);}  
13. }  

接著只要把 n 轉成二進位的字串後, 略過最左邊的位數後由左往右將每個位數傳入 move() 函數便可以得到問題一的答案. 

至於問題二: 

2. Given p/q, find its position in the array. As an example, the input 1/2 results in the output 2.

就使用反推的思維, 當 p>q 說明當上一次是由父節點的右邊移動; 如果 q>p 說明上一次是由父節點的左邊移動. 如此你可以得到行走的路徑, 跟據 0->往左邊; 1->往右邊 將之轉換成二進位後記得要反轉 (因為現在是倒著走 Orz). 所以問題二的類別如下: 

view plaincopy to clipboardprint?

1. public static class P2{  
2.     public long p=0;  
3.     public long q=0;  
4.       
5.     public P2(long p, long q){this.p = p; this.q = q;}  
6.       
7.     public String run()  
8.     {  
9.         int loop=0;  
10.         StringBuffer strBuf = new StringBuffer();  
11.         while(true)  
12.         {  
13.             if(p==1 && q==1) break;  
14.             else if(p>q)  
15.             {  
16.                 strBuf.append("1");  
17.                 p = p-q;  
18.             }  
19.             else  
20.             {  
21.                 strBuf.append("0");  
22.                 q = q-p;  
23.             }  
24.             loop++;  
25.             if(loop==Integer.MAX_VALUE) System.err.printf("\t[Error] Exceed Int Max!\n");  
26.         }  
27.           
28.         if(loop==0) return "1";  
29.         else {                
30.             BigInteger bi1 = new BigInteger(new StringBuilder(strBuf.toString()).reverse().toString(), 2);  
31.             BigInteger bi2 = new BigInteger("2");  
32.             bi1.add(bi2.pow(loop));               
33.             return bi1.add(bi2.pow(loop)).toString();  
34.         }             
35.     }  
36. }  

最後整個問題的代碼如下: 

view plaincopy to clipboardprint?

1. package cj2014;  
2.   
3. import java.math.BigInteger;  
4.   
5. import flib.util.io.QSReader;  
6. import flib.util.io.QSWriter;  
7.   
8. public class PB {  
9.     public static class P1{  
10.         public long p=1;  
11.         public long q=1;  
12.           
13.         public void move(char c)  
14.         {  
15.             if(c=='0') q = p+q;           
16.             else p = p+q;             
17.         }  
18.           
19.         @Override  
20.         public String toString() {return String.format("%d %d", p,q);}  
21.     }  
22.       
23.     public static class P2{  
24.         public long p=0;  
25.         public long q=0;  
26.           
27.         public P2(long p, long q){this.p = p; this.q = q;}  
28.           
29.         public String run()  
30.         {  
31.             int loop=0;  
32.             StringBuffer strBuf = new StringBuffer();  
33.             while(true)  
34.             {  
35.                 if(p==1 && q==1) break;  
36.                 else if(p>q)  
37.                 {  
38.                     strBuf.append("1");  
39.                     p = p-q;  
40.                 }  
41.                 else  
42.                 {  
43.                     strBuf.append("0");  
44.                     q = q-p;  
45.                 }  
46.                 loop++;  
47.                 if(loop==Integer.MAX_VALUE) System.err.printf("\t[Error] Exceed Int Max!\n");  
48.             }  
49.               
50.             if(loop==0) return "1";  
51.             else {                
52.                 BigInteger bi1 = new BigInteger(new StringBuilder(strBuf.toString()).reverse().toString(), 2);  
53.                 BigInteger bi2 = new BigInteger("2");  
54.                 bi1.add(bi2.pow(loop));               
55.                 return bi1.add(bi2.pow(loop)).toString();  
56.             }             
57.         }  
58.     }  
59.   
60.     /** 
61.      * BD: https://code.google.com/codejam/contest/2924486/dashboard#s=p1 
62.      * @param args 
63.      */  
64.     public static void main(String[] args) throws Exception{  
65.         String fn="B-large-practice.in";  
66.         QSReader qsr = new QSReader(String.format("data/2014/%s", fn));  
67.         QSWriter qsw = new QSWriter(String.format("data/2014/%s.out", fn));  
68.         qsr.open();       
69.         Integer pc = Integer.valueOf(qsr.line());  
70.         System.out.printf("\t[Info] Total %d question...\n", pc);  
71.         for(int i=1; i<=pc; i++)  
72.         {  
73.             String ps[] = qsr.line().split(" ");  
74.             if(ps[0].equals("1"))  
75.             {  
76.                 // If the problem id is 1, then only one integer n is given,   
77.                 // and you are expected to find the n-th element of the array.                
78.                 try  
79.                 {  
80.                     char[] actions;  
81.                     actions = Long.toBinaryString(Long.valueOf(ps[1])).toCharArray();  
82.                     if(ps[1].length()>18) actions = new BigInteger(ps[1]).toString(2).toCharArray();  
83.                     else actions = Long.toBinaryString(Long.valueOf(ps[1])).toCharArray();  
84.                     P1 p1 = new P1();  
85.                     for(int j=1; j
86.                     System.out.printf("\t\tP1: %s -> %s\n", ps[1], p1);  
87.                     qsw.line(String.format("Case #%d: %s", i, p1.toString()));  
88.                 }  
89.                 catch(Exception e)   
90.                 {  
91.                     System.out.printf("\t[Error] %s\n", e.toString());  
92.                     qsw.line(String.format("Case #%d: -1", i));  
93.                 }  
94.             }  
95.             else if(ps[0].equals("2"))  
96.             {  
97.                 // If the problem id is 2,   
98.                 // then two integers p and q are given, and you are expected to find the position of p/q in the array.  
99.                 P2 p2 = new P2(Long.valueOf(ps[1]), Long.valueOf(ps[2]));  
100.                 String asw = p2.run();  
101.                 System.out.printf("\t\tP2: %s %s -> %s\n", ps[1], ps[2], asw);  
102.                 qsw.line(String.format("Case #%d: %s", i, asw));  
103.             }  
104.         }  
105.         qsr.close();  
106.         qsw.close();  
107.     }  
108.   
109. }  

Supplement: 
* [ Java 文章收集 ] BigInteger 的使用