371 - Ackermann Functions

[pok]

Why WA ?
pls help me..

Code: Select all

removed after AC..

[Articuno]

@pok,
Your code will not work for input like this:

Code: Select all

10 1

You did not consider this.
The output should be:

Code: Select all

Between 1 and 10, 9 generates the longest sequence of 19 values.

Wish you good luck.

[pok]

Thanks Articuno..
now my code is AC..
take care..
God bless you..

[sazzadcsedu]

what is the input limit for this problem??
plz someone tell me.

[mf]

what is the input limit for this problem??
plz someone tell me.

"The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long" - that sounds like an good enough specification of input limits to me.

You can immediately deduce that the inputs will fit in 32-bit integers. And if you spend some time calculating on your PC the maximum number in the sequence for every 32-bit starting number, you'll even obtain the maximum allowed difference between the two inputs numbers. I don't think it'll be very large.

[theharshest]

Even after using memoization I am getting TLE...
Please help..

Code: Select all

#include<iostream>
#include<map>
#include<cmath>
using namespace std;

int main()
{
	long long m,n;
	map<long long,long long> mp;
	long long c;
	long long max1,max2;
	mp[1]=3;

	while(1)
	{
		scanf("%lld %lld",&m,&n);
		if(m==0 && n==0)
			break;

		max1=0;
		max2=0;
		for(long long i=min(m,n);i<=max(m,n);i++)
		{
			c=0;
			long long tmp=i;
			if(mp[i])
				c=mp[i];
			else
			{
			while(i!=1)
			{
				c++;
				if(i%2==0)
					i/=2;
				else
					i=3*i+1;
			}

			mp[tmp]=c;
			}
			if(c>max2)
			{
				max2=c;
				max1=tmp;
			}
		}

		printf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n",min(m,n),max(m,n),max1,max2);
	}
}

[Chirag Chheda]

this one is same as the 3n+1 problem
memorization can be done by the following way:- Suppose u are calculating the cycle length of a number 'a' and during this u arrive to an intermediate value b whose cycle length had been found initially den just add the the cycle length of b to the current length of 'a' to get the final cycle length.

Hope it helps

[theharshest]

Even then i am getting TLE..

i have commented at proper places.. pls check

Code: Select all

#include<iostream>
#include<map>
#include<cmath>
using namespace std;

int main()
{
	long long m,n;
	map<long long,long long> mp;
	long long c;
	long long max1,max2;
	mp[1]=3;

	while(1)
	{
		scanf("%lld %lld",&m,&n);
		if(m==0 && n==0)
			break;

		max1=0;
		max2=0;
		for(long long i=min(m,n);i<=max(m,n);i++)
		{
			c=0;
			long long tmp=i;
			if(mp[i]) // checking if the cycle already calculated
				c=mp[i];
			else
			{
			while(i!=1)
			{
				c++;
				if(i%2==0)
					i/=2;
				else
					i=3*i+1;

				if(mp[i] && i!=1) // here i am adding the sub-cycle i previously calculated
				{
					c+=mp[i];
					break;
				}
			}

			mp[tmp]=c; // here i m memoizing
			}
			if(c>max2)
			{
				max2=c;
				max1=tmp;
			}
		}

		printf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n",min(m,n),max(m,n),max1,max2);
	}
}

[redrumpeace]

Hello, desperate here.. It got TLE..

Here is my code

Code: Select all

# include <stdio.h>
# include <stdlib.h>

int ackerman (long long number)
{
    int count = 0;
    
    do
    {
        if ((number % 2) == 0)  number = number/2;
        else                    number = (number*3) + 1;
        
        count++;
    }
    while (number != 1);
    return (count);
}

int main ()
{
    long long start, end;
    int max;
    long long number;
    int result;
    
    while (scanf("%I64d %I64d", &start, &end) == 2)
    {
        if ((start == 0) && (end == 0)) break;
        
        max = 0;
        
        if (start > end) start ^= end ^= start ^= end;
        
        for (long long i = start; i <= end; i++)
        {
            result = ackerman(i);
            if (result > max)
            {
                number = i;
                max = result;
            }
        }
        printf ("Between %I64d and %I64d, %I64d generates the longest sequence of %d values.\n", start, end, number, max);
    }
}

For this input

Code: Select all

1 2
1 10000
30000 100000
1 1000000
2000000000 2001000000
1234567890 1235678901
0 0

The output is

Code: Select all

Between 1 and 2, 1 generates the longest sequence of 3 values.
Between 1 and 10000, 6171 generates the longest sequence of 261 values.
Between 30000 and 100000, 77031 generates the longest sequence of 350 values.
Between 1 and 1000000, 837799 generates the longest sequence of 524 values.
Between 2000000000 and 2001000000, 2000001502 generates the longest sequence of 804 values.
Between 1234567890 and 1235678901, 1234593769 generates the longest sequence of 731 values.

Any help is apreciated.. Thx..

[redrumpeace]

Hello, desperate here.. It got TLE..

Here is my code

Code: Select all

# include <stdio.h>
# include <stdlib.h>

int ackerman (long long number)
{
    int count = 0;
    
    do
    {
        if ((number % 2) == 0)  number = number/2;
        else                    number = (number*3) + 1;
        
        count++;
    }
    while (number != 1);
    return (count);
}

int main ()
{
    long long start, end;
    int max;
    long long number;
    int result;
    
    while (scanf("%I64d %I64d", &start, &end) == 2)
    {
        if ((start == 0) && (end == 0)) break;
        
        max = 0;
        
        if (start > end) start ^= end ^= start ^= end;
        
        for (long long i = start; i <= end; i++)
        {
            result = ackerman(i);
            if (result > max)
            {
                number = i;
                max = result;
            }
        }
        printf ("Between %I64d and %I64d, %I64d generates the longest sequence of %d values.\n", start, end, number, max);
    }
}

For this input

Code: Select all

1 2
1 10000
30000 100000
1 1000000
2000000000 2001000000
1234567890 1235678901
0 0

The output is

Code: Select all

Between 1 and 2, 1 generates the longest sequence of 3 values.
Between 1 and 10000, 6171 generates the longest sequence of 261 values.
Between 30000 and 100000, 77031 generates the longest sequence of 350 values.
Between 1 and 1000000, 837799 generates the longest sequence of 524 values.
Between 2000000000 and 2001000000, 2000001502 generates the longest sequence of 804 values.
Between 1234567890 and 1235678901, 1234593769 generates the longest sequence of 731 values.

Any help is apreciated.. Thx..

[mf]

Heed compiler warnings:

p.cc: In function ‘int main()’:
p.cc:26: warning: format ‘%I64d’ expects type ‘int*’, but argument 2 has type ‘long long int*’
p.cc:26: warning: format ‘%I64d’ expects type ‘int*’, but argument 3 has type ‘long long int*’
p.cc:32: warning: operation on ‘start’ may be undefined (there's another predefined symbol 'start', you don't want to mess with it)
p.cc:43: warning: format ‘%I64d’ expects type ‘int’, but argument 2 has type ‘long long int’
p.cc:43: warning: format ‘%I64d’ expects type ‘int’, but argument 3 has type ‘long long int’
p.cc:43: warning: format ‘%I64d’ expects type ‘int’, but argument 4 has type ‘long long int’
p.cc:23: warning: ‘number’ may be used uninitialized in this function

The output is...

No, it isn't! Your output is screwed up on Linux, because %I64d is not a standard printf specifier for type 'long long'.

[Azad Salam]

getting Runtime error again and again.......i changed the array size{list} and also have used long long......but all the time the program gets RTE...it runs for 0.000 seconds......I dont think the problem is with the array size or using long or long long.....

PLS HELP....THNX IN ADVANCE....

here is my code {in C}


#include<stdio.h>

int main()
{ long list[42949],i,n,tmp,a,b,ans1,ans2;
list[0]=0;
list[1]=3;
list[2]=1;
for(i=3;i<42949;i++)
{ tmp=0;
for(n=i;n!=1;tmp++)
{ if(n<i)
{ tmp+=list[n]-1;
n=1;
}
else
{ if(n%2)
n=3*n+1;
else
n/=2;
}
}
list=tmp;
}
while(scanf("%ld %ld",&a,&b)==2 && (a || b))
{ if(a>b)
{ tmp=a;
a=b;
b=tmp;
}
tmp=0;

for(i=b;i>=a;i--)
{ if(list>=tmp)
{ tmp=list;
ans1=i;
ans2=list;
}
}
printf("Between %ld and %ld, %ld generates the longest sequence of %ld values.\n",a,b,ans1,ans2);

}
return 0;
}




This is my first post in the forum...So please please help me ...THnx in Advance

[Jehad Uddin]

dont make list,just calculate lyk 3n+1 (uva100) and use unsigned int in c++ or unsigned long in ansiC,
and another thing always make arrays outside main() (globally declare )

[Azad Salam]

Thnx jehad for ur help...now got ac :D

[etameem]

here is my code:

Code: Select all

#include <iostream>

using namespace std;

int main()
{

int count=0,max=0,temp;
long int i,j,k,p,gen=0;

while(scanf("%ld %ld",&i,&j)==2)
{
    if(i==0&&j==0)
    break;

    if(i>j)
    {temp=i;
    i=j;
    j=temp;


        }

    max=0;
    gen=0;

for (k=i;k<=j;k++)
	{
	p=k;
	while (p!=1)
	{
		if (p%2==0)
		p=p/2;
		else
		p=3*p+1;

		count=count+1;
	}
	if (k==1)
	{count=1;}



	if(max<count)
	{max=count;
	gen=k;
	}

		count=0;


	}





	printf("Between %ld and %ld, %ld generates the longest sequence of %ld values.\n",i,j,gen,max);


}
return 0;
}

i am getting WA. please help me to find where the problem is...