Advertisement
Guest User

Untitled

a guest
Sep 28th, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.36 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. int cycleLength(long long int);
  5.  
  6. int cycleLengthResult[1000001];
  7.  
  8. int main(int argc, char *argv[])
  9. {
  10. int i = 0, j = 0, cur = 0, max = 0, k = 0, s = 0;
  11. for (i = 1 ; i < 1000001 ; ++ i ) cycleLength(i);
  12.  
  13. while ( scanf("%d%d", &i, &j) != EOF )
  14. {
  15. printf("%d %d ", i, j);
  16. if ( i > j )
  17. {
  18. s = i;
  19. i = j;
  20. j = s;
  21. }
  22. max = 0;
  23. for ( k = i ; k <= j ; ++ k )
  24. {
  25. cur = cycleLengthResult[k];
  26. if (cur > max) max = cur;
  27. }
  28. printf("%dn", max);
  29. }
  30.  
  31. return 0;
  32. }
  33.  
  34. int cycleLength(long long int arg)
  35. {
  36. if ( arg > 1000000 )
  37. {
  38. if (!(arg & 1))
  39. return 1 + cycleLength(arg/2);
  40. else
  41. return 1 + cycleLength(arg*3+1);
  42. }
  43. if (!cycleLengthResult[arg])
  44. {
  45. int valueForArg = 0;
  46. if (arg == 1)
  47. valueForArg = 1;
  48. else if (!(arg & 1))
  49. valueForArg = 1 + cycleLength(arg/2);
  50. else
  51. valueForArg = 1 + cycleLength(arg*3+1);
  52.  
  53. cycleLengthResult[arg] = valueForArg;
  54. }
  55. return cycleLengthResult[arg];
  56. }
  57.  
  58. t(n) = 1 if n is 1
  59. = 3n + 1 if n is odd
  60. = n / 2 if n is even
  61.  
  62. c(n) = number of times t(n) will happen
  63. (terrible math syntax here, but erm... go with it)
  64.  
  65. for (int i = 1; i <= 1000000; ++i) {
  66. if (i % 2 == 0) {
  67. //We know that i / 2 must already be set, so we can just do a constant time look up
  68. //(your code already does this implicitly through the recursion)
  69. m[i] = 1 + m[i / 2];
  70. } else {
  71. m[i] = cycleLength(i);
  72. }
  73. }
  74.  
  75. if (i % 2 == 0) {
  76. m[i] = 1 + m[i/2];
  77. } else if (i % 8 == 5) {
  78. m[i] = 4 + m[3 * ((i - 5) / 8) + 2];
  79. } else {
  80. m[i] = cycleLength(i);
  81. }
  82.  
  83. 8j + 5 -> 24j + 16 -> 12j + 8 -> 6j + 4 -> 3j + 2
  84.  
  85. int cycleLength(long arg);
  86.  
  87. static inline int nextLength(long arg)
  88. {
  89. long n;
  90. if (arg & 1) {
  91. n = (arg * 3) + 1;
  92. } else {
  93. n = arg / 2;
  94. }
  95. return 1 + cycleLength(n);
  96. }
  97.  
  98. int cycleLength(long arg)
  99. {
  100. if (arg > 10000000) {
  101. return nextLength(arg);
  102. }
  103. if (cycleLengthResult[arg] != 0) {
  104. return cycleLengthResult[arg];
  105. }
  106. return cycleLengthResult[arg] = nextLength(arg);
  107. }
  108.  
  109. #include <cstdio>
  110. #include <algorithm> // std::min, std::max
  111. using namespace std;
  112.  
  113. int cycleLength(int);
  114. const int CACHE_LEN = 1000001;
  115. short cache[CACHE_LEN] = {0};
  116.  
  117. int main()
  118. {
  119. int leftNo, rightNo, minNo, maxNo;
  120. while ( scanf("%d%d", &leftNo, &rightNo) != EOF )
  121. {
  122. int maxCycles = 0;
  123. minNo = min(leftNo, rightNo);
  124. maxNo = max(leftNo, rightNo);
  125. for (int curNo = minNo; curNo <= maxNo; ++curNo )
  126. {
  127. int curCycles = cycleLength(curNo);
  128. if (curCycles > maxCycles) maxCycles = curCycles;
  129. }
  130. printf("%d %d %dn", leftNo, rightNo, maxCycles);
  131. }
  132. return 0;
  133. }
  134.  
  135. int cycleLength(int start)
  136. {
  137. int length = cache[start];
  138. if (length != 0) return length;
  139. length++;
  140. long long int current = start;
  141. while (current != 1)
  142. {
  143. if (current % 2 == 0) current /= 2;
  144. else current = 3 * current + 1;
  145. length++;
  146. }
  147. cache[start] = length;
  148. return length;
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement