fork download
copy 
  1. // Runs in 0.03 sec
  2.  
  3. #include <cstdint>
  4. #include <iostream>
  5. #include <vector>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. int main();
  10.  
  11. typedef uint_fast32_t number;
  12. typedef uint_fast32_t sequencelength;
  13.  
  14. const size_t cachesize = 0x100000;
  15. vector<sequencelength> t(cachesize, 0);
  16.  
  17. typedef uint_fast32_t index;
  18. number indextonumber(index);
  19. index numbertoindex(number);
  20. const number maxcachednumber = indextonumber(cachesize-1);
  21.  
  22. void arrange(number&, number&);
  23.  
  24. sequencelength getlength(number);
  25.  
  26. int main()
  27. {
  28.   ios_base::sync_with_stdio(false);
  29.  
  30.   number i, j;
  31.   while(cin >> i >> j)
  32.   {
  33.     cout << i << ' ' << j << ' ';
  34.  
  35.     sequencelength maxlength = 0;
  36.     for(arrange(i, j); i<=j; ++i)
  37.       if(getlength(i) > maxlength)
  38.         maxlength = getlength(i);
  39.  
  40.     cout << maxlength << '\n';
  41.   }
  42.  
  43.   return 0;
  44. }
  45.  
  46. sequencelength getlength(number i)
  47. {
  48.   number next = i%2 == 0 ? i/2 : 3*i+1;
  49.  
  50.   if(i>maxcachednumber)
  51.     return getlength(next)+1;
  52.  
  53.   if(t[numbertoindex(i)] == 0)
  54.     t[numbertoindex(i)] = i == 1 ? 1 : getlength(next) + 1;
  55.  
  56.   return t[numbertoindex(i)];
  57. }
  58.  
  59. void arrange(number &i, number &j)
  60. {
  61.   if(i > j)
  62.     swap(i, j);
  63. }
  64.  
  65. number indextonumber(index i)
  66. {
  67.   return i+1;
  68. }
  69.  
  70. index numbertoindex(number i)
  71. {
  72.   return i-1;
  73. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
1 10
100 200
201 210
900 1000
stdout
copy 
1 10 20
100 200 125
201 210 89
900 1000 174
https://ideone.com/CEgpur
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!