Advertisement
Guest User

Untitled

a guest
Sep 22nd, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.33 KB | None | 0 0
  1. #include <stdio.h>
  2. #define FOR(a,b,c) for(long long a = b ; a < c ; ++a)
  3. #define MEMO_SIZE 1000005
  4.  
  5. long memoization[MEMO_SIZE] = {0};
  6.  
  7. long long max (long long a, long long b) {
  8. return a > b ? a : b;
  9. }
  10.  
  11. long long min (long long a, long long b) {
  12. return a < b ? a : b;
  13. }
  14.  
  15. int isEven (long long n) {
  16. return n % 2 == 0;
  17. }
  18.  
  19. int canBeMemoized (long long n) {
  20. return n < MEMO_SIZE;
  21. }
  22.  
  23. int isNotMemoizedYet (long long n) {
  24. return canBeMemoized(n) && memoization[ (int) n ] == 0;
  25. }
  26.  
  27. int isMemoized (long long n) {
  28. return canBeMemoized(n) && memoization[ (int) n ] != 0;
  29. }
  30.  
  31. long long solution (long long n) {
  32. if (isMemoized(n)) return memoization[ (int) n ];
  33.  
  34. int result = 1;
  35.  
  36. while (n != 1) {
  37. if ( isEven(n) ) n /= 2;
  38. else {
  39. n = ((n*3) + 1) / 2;
  40. ++result;
  41. }
  42.  
  43. ++result;
  44. }
  45.  
  46. if (isNotMemoizedYet(n)) {
  47. memoization[ (int) n] = result;
  48. }
  49.  
  50. return result;
  51. }
  52.  
  53. long long countingN (long long a, long long b) {
  54. long long lower = min(a, b);
  55. long long upper = max(a, b);
  56.  
  57. long long maximum = 0;
  58.  
  59. FOR(i,lower,upper+1) {
  60. long long n = solution(i);
  61. maximum = max(maximum, n);
  62. }
  63.  
  64. return maximum;
  65. }
  66.  
  67. int main () {
  68. long long a, b, n;
  69.  
  70. while (scanf("%lld %lld", &a, &b) == 2) {
  71. printf("%lld\n", countingN(a, b));
  72. }
  73. return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement