# Hi Raed :)

Aug 16th, 2021
1,462
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*********************
2. * My Solution Explane:
3. *
4. * 1) We can first preprocess all numbers [1 <-> 1000000]
5. *
6. * 2) We have an observation (By see the results of preprocessing):
7. *       The maximum length between [1 <-> 1000000] = 525.
8. *       So we can make a loop from 1 -> 1000000 and store the
9. *       length of cycle that start with i in array caled "len[MaxInput]"
10. *
11. * 3) Now we have all lengths before reading any input.
12. *
13. * 4) We can using "Segment_Tree" or "Sparse Table" To get the
14. *    Range Maximum Query (RMQ) between i and j (input numbers).
15. *       Note:
16. *           - I'm using segment tree because the number of test cases
17. *             is unknown from the problem statement.
18. *           - Maybe it can get accepted using brute force only ,
19. *             if the number of test cases is less than 100.
20. *           - using Segment tree can get the ans of query in O(logN)
21. *
22. * Thanks for the great competition AmesCom.
23. *
24. * Author: Ismaeil Al-refaey.
25. ***************************/
26.
27. #include <bits/stdc++.h>
28.
29. using namespace std;
30.
31. const int N = 1e6 + 4e1;
32.
33. /// Array that have in index i the
35. int len[N];
36.
37. /// --- SegmentTree for RMQ (Range Maximum Query) --- ///
38. class SegTree
39. {
40.     #define lf (p << 1) // left child
41.     #define rg (lf | 1) // right child
42.
43.     private:
44.         vector< int > Seg;
45.
46.         void compain(int &res ,int l , int r)
47.         {
48.             res = max(l ,r);
49.         }
50.
51.         void BLD(int p ,int L ,int R)
52.         {
53.             if( L == R )
54.             {
55.                 Seg[p] = len[L];
56.                 return;
57.             }
58.
59.             int Mid = (L + R) >> 1;
60.             BLD(lf ,L ,Mid);
61.             BLD(rg ,Mid + 1 ,R);
62.             compain(Seg[p] ,Seg[lf] ,Seg[rg]);
63.         }
64.
65.         int QRY(int i ,int j ,int p ,int L ,int R)
66.         {
67.             if( R <  i || L >  j ) return INT_MIN;
68.             if( i <= L && R <= j ) return Seg[p];
69.
70.             int Mid = (L + R) >> 1 ,res;
71.             int LF = QRY(i ,j ,lf ,L ,Mid);
72.             int RG = QRY(i ,j ,rg ,Mid + 1 ,R);
73.             compain(res ,LF ,RG);
74.             return res;
75.         }
76.
77.     public:
78.         SegTree(int n)
79.         {
80.             Seg.assign(4 * n ,INT_MIN);
81.         }
82.
83.         void BLD()
84.         {
85.             BLD(1 ,1 ,N - 1);
86.         }
87.
88.         /// --- Function to get RMQ between (i ,j)
89.         int QRY(int i ,int j)
90.         {
91.             return QRY(i ,j ,1 ,1 ,N - 1);
92.         }
93. };
94.
95. /// --- This function calc the length of cycle that start with n --- ///
96. int getLen(int64_t n)
97. {
98.     int lenOfSequence = 1;
99.
100.     /// --- Implement the operations --- ///
101.     while( n > 1 )
102.     {
103.         if( n <= 1 ) break;
104.         if( n & 1 )
105.         {
106.             n *= 3;
107.             n += 1;
108.         }
109.         else n /= 2;
110.
111.         lenOfSequence += 1;
112.     }
113.
114.     return lenOfSequence;
115. }
116.
117. int main()
118. {
119.     /// --- PreProcessing lengths --- ///
120.     for(int i = 1 ; i < N ; i++) len[i] = getLen(i);
121.
122.     /// --- Maximum Segment Tree --- ///
123.     SegTree st(N + 1);
124.     st.BLD();
125.
126.     int i ,j;
127.     /// --- Querys processing --- ///
128.     while( scanf("%d%d" ,&i ,&j) != EOF )
129.     {
130.         /// --- print the correct i,j --- ///
131.         printf("%d %d " ,i ,j);
132.
133.         if( i > j ) swap(i ,j);
134.
135.         /// --- Get the max length between i and j using segment tree --- ///
136.         int maxLen = st.QRY(i ,j);
137.
138.         /// --- Output --- ///
139.         printf("%d\n" ,maxLen);
140.     }
141. }
142.