# UVA100[The 3n + 1 problem]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-5-13

DESCRIPTION:

\$DESCRIPTION

*/

#include <stdio.h>

#define MAXN 1000000

int f[MAXN+2];

int st[MAXN<<2];

int max(int a,int b)

{

return a>b?a:b;

}

void build_segment_tree(int L=1,int R=MAXN,int root=1)

{

if (L==R) st[root]=f[L];

else

{

int LL=L,LR=(L+R)>>1,Lroot=root<<1;

int RL=LR+1,RR=R,Rroot=Lroot|1;

build_segment_tree(LL,LR,Lroot);

build_segment_tree(RL,RR,Rroot);

st[root]=max(st[Lroot],st[Rroot]);

}

}

int get_max(int l,int r,int L=1,int R=MAXN,int root=1)

{

if (r<L||l>R) return 0;

if (l<=L&&R<=r) return st[root];

else

{

int LL=L,LR=(L+R)>>1,Lroot=root<<1;

int RL=LR+1,RR=R,Rroot=Lroot|1;

return max(get_max(l,r,LL,LR,Lroot),

get_max(l,r,RL,RR,Rroot));

}

}

int main()

{

f[1]=1;

for (int i=2;i<=MAXN;i++)

{

long long int n=i;

int step=0;

for (;;)

{

if (n<=MAXN&&f[n])

{

step+=f[n];

break;

}

step++;

if (n&1) n=((n<<1)|1)+n;

else n>>=1;

}

f[i]=step;

}

build_segment_tree();

int i,j;

while (scanf(“%d%d”,&i,&j)!=EOF)

if (i<=j) printf(“%d %d %d\n”,i,j,get_max(i,j));

else printf(“%d %d %d\n”,i,j,get_max(j,i));

return 0;

}