## 2013年9月25日 星期三

### [ 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.

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

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

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. }

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

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==1break;
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==0return "1";
29.         else {
30.             BigInteger bi1 = new BigInteger(new StringBuilder(strBuf.toString()).reverse().toString(), 2);
31.             BigInteger bi2 = new BigInteger("2");
34.         }
35.     }
36. }

1. package cj2014;
2.
3. import java.math.BigInteger;
4.
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==1break;
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==0return "1";
51.             else {
52.                 BigInteger bi1 = new BigInteger(new StringBuilder(strBuf.toString()).reverse().toString(), 2);
53.                 BigInteger bi2 = new BigInteger("2");
56.             }
57.         }
58.     }
59.
60.     /**
62.      * @param args
63.      */
64.     public static void main(String[] args) throws Exception{
65.         String fn="B-large-practice.in";
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 的使用

### [ Python 文章收集 ] List Comprehensions and Generator Expressions

Source From  Here   Preface   Do you know the difference between the following syntax?  view plain copy to clipboard print ? [x  for ...