Sunday, 13 May 2012

UVa 371 Ackermann Functions Solution

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
using namespace std;

int main()
{
long long p,t,y,x,i,z,max,n;
map<long long,long long>nt;
map<long long,long long>a;
while(cin>>x>>y)
    {
    if(x==0 && y==0) return 0;
    if(x>y){
           n=x;
           x=y;
           y=n;
           }
    z=0;
    nt.clear();
    a.clear();
    for(i=x;i<=y;i++)
        {
        p=i;
        t=0;
        while(1)
            {
            if(p%2==0) {
                        p/=2;
                        t++;
                        }
            else {
                 p=(3*p)+1;
                 t++;
                 }
            if(p==1) break;
            }
        if(a[t]!=1) {
                    nt[t]=i;
                    a[t]=1;
                    }
        if(z==0){
                max=t;
                z++;
                }
        else if(max<t) max=t;
        }
    cout<<"Between "<<x<<" and "<<y<<", "<<nt[max]<<" generates the longest sequence of "<<max<<" values."<<endl;
    }
return 0;
}

2 comments: