371 - Ackermann Functions

[brianfry713]

remove the saver and you will get AC.

[kia.masster]

Thank you Brian...

[brianfry713]

Input:

Code: Select all

1 2
0 0

AC output:

Code: Select all

Between 1 and 2, 1 generates the longest sequence of 3 values.

[jocker1]

Yeah you were right brian, i forgot that case completely....
Thanks a lot brianfry problem AC.......

[vpanait]

i consider the problem statement a bit confusing, I got AC only after I've taken care that the input pair is ordered [L H]. Ex:
1 2
2 1
mean the same thing, and both are valid input.

enjoy

[gr81]

did some one test this test case
3 2147483647

how long it will take.....

[gr81]

I am getting TLE...in above test case.

[brianfry713]

That input is not valid. The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long.

[gr81]

thanks for clarification, but issue was something else...got AC.

[atiburrahman09]

hello friend i tried to handle the case 1 2.but when i input the file output never comes.can anyone help me.

here is my code...

#include<iostream>
using namespace std;
int main()
{
long long int x, y,i,count,max=0,v,n=0,temp;
while(cin>>x>>y)
{
max=0;
if(x==0 && y==0)
break;
if(y<x)
{
temp=x;
x=y;
y=temp;
}

for(i=x; i<=y; i++)
{

count=0;
while(n!=1)
{
n=i;
if(n%2==0)
{
n=n/2;
count++;
}
else
{
n=(3*n+1);
count++;
}

if(max < count)
{
max=count;

v = i;
}
}
}
cout<<"Between "<<x<<" and " <<y <<", "<< v <<" generates the longest sequence of "<<max<<" values."<<endl;
}


return 0;
}

[brianfry713]

Try changing lines 22-24 from:

Code: Select all

while(n!=1)
{
n=i;

to:

Code: Select all

n=i;
while(n!=1)
{

[alimbubt]

The only tricky test case for this problem is
Input:

Code: Select all

1 2

Output:

Code: Select all

Between 1 and 2, 1 generates the longest sequence of 3 values.

[shipu_a]

TLE plz help.....................

Code: Select all

#include<iostream>
#include<algorithm>
#include<sstream>
#include<fstream>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#define ll long long
#define sc scanf
#define pf printf
#define pi 2*acos(0.0)
using namespace std;
int main()
{
    ll m,n,a,b,c,Max,Gn;
    while(sc("%lld%lld",&m,&n)==2)
    {
        Max=0;
        if(m==0&&n==0)
        break;
        a=min(m,n);
        b=max(m,n);
        for(ll i=a;i<=b;i++)
        {
            int p=i;
            c=0;
            if(p%2==0)
            {
                p/=2;
                c++;
            }
            else
            {
                p=3*p+1;
                c++;
            }
            while(p!=1)
            {
                if(p%2==0)
                {
                    p/=2;
                    c++;
                }
                else
                {
                    p=3*p+1;
                    c++;
                }

            }
            if(c>Max)
            {
                Max=c;
                Gn=i;
            }
        }

        pf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n",a,b,Gn,Max);

    }
    return 0;
}

[lbv]

TLE plz help.....................

Reading comprehension can be tricky sometimes, but it's a skill that requires plenty of attention when solving algorithm problems. For example, in this problem, think about the meaning of this sentence (from the problem statement):

The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long.

At first, you might think that using a 32-bit signed integer might work, but actually, the problem statement says nothing about a signed 32-bit integer, so it's a good idea not to assume that it should be signed. Hence, try for example changing the type of your p variable from "int" to "unsigned int".

Try for example this case:

Code: Select all

800000 900000
0 0

Code: Select all

Between 800000 and 900000, 837799 generates the longest sequence of 524 values.

[sakibrahman]

#include <stdio.h>
#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
using namespace std;
long long int sequence[10000000+5];
long long int seq2[10000000+5];
long long int ackerman(long long int a)
{
long long int sequence = 0;
if(a==1) sequence = 3;
else
{
while(a!=1)
{
if(a%2==0) a = a / 2;
else a = 3 * a +1;
sequence++;
}
}

return sequence;


}


int main()
{

long long int i,j,k,m,n,o,p,q,a,b;
while(scanf("%lld %lld",&a,&b)&&a!=0&&b!=0)
{
if(a>b) {m = a;a = b; b = m;}
for(i=a;i<=b;i++)
{
sequence = ackerman(i);
}



i=a;
for(k = 0; k<(b-a);k++)
{
seq2[k] = sequence;
i++;
}
sort(seq2,seq2+k);
long long int largest = seq2[k-1];


i = a;
while(i!=b+1)
{
// cout<<i<<": "<<sequence<<endl;
if(sequence==largest)
{
printf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n",a, b, i, largest);
break;
}
i++;
}

}




}


I'm just blushed out and dissapointed!