SPOJ PROBTNPO

When I saw this problem for the first time memoization was the word that came to my mind. And as usual, I jumped into coding it without giving it much thought before it struck me that a static memo is not a very good option as the numbers might go out of bounds because off the 3*n+1 step. Then I resorted to using map, a fancy but very useful data structure. But the "Man proposes, God disposes and I slog" rule came into play and I got some runtime errors, thanks to my flamboyant coding skills ;-) . Next came a tsunami of TLEs. After sometime i got really frustrated and started typing afresh right into the "code pasting" text field. It was the most naive solution I could think of and expected a TLE. But to my surprise, there it was smiling at me, a beautiful ACC.

#include <cstdio>

#include <algorithm>

using namespace std;

int f(int i)

{

int cnt = 1;

while(i != 1) {

if(i&1) cnt+=2,i=(3*i+1)>>1;

else ++cnt,i=i>>1;

}

return cnt;

}

int main()

{

int i, j, a;

int mx;

while(scanf("%d%d", &i, &j)!=EOF) {

mx = -1;

for(a=min(i,j); a<=max(i,j); ++a)

mx = max(mx, f(a));

printf("%d %d %d\n", i, j, mx);

}

return 0;

}