371 - Ackermann Functions

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 371 - Anckerman Functions - Why WA ?

Post by pok » Mon Dec 15, 2008 12:57 am

Why WA ?
pls help me..

Code: Select all

removed after AC..
Last edited by pok on Sat Dec 20, 2008 10:05 pm, edited 1 time in total.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 371 - Anckerman Functions - Why WA ?

Post by Articuno » Fri Dec 19, 2008 3:42 pm

@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.
May be tomorrow is a better day............ :)

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 371 - Anckerman Functions - Why WA ?

Post by pok » Sat Dec 20, 2008 10:26 pm

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

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

371 - Anckerman Functions - input limit ?

Post by sazzadcsedu » Sun Dec 28, 2008 10:58 pm

what is the input limit for this problem??
plz someone tell me.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 371 - Anckerman Functions - Why WA ?

Post by mf » Sun Dec 28, 2008 11:37 pm

sazzadcsedu wrote: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.

User avatar
theharshest
New poster
Posts: 20
Joined: Thu Jan 17, 2008 10:47 pm
Location: India

Re: 371 - Ackermann Functions #TLE. Please Help!

Post by theharshest » Wed Mar 11, 2009 8:27 pm

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);
	}
}
"if u r goin thru hell, keep goin"

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 371 - Ackermann Functions #TLE. Please Help!

Post by Chirag Chheda » Wed Mar 11, 2009 8:50 pm

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

User avatar
theharshest
New poster
Posts: 20
Joined: Thu Jan 17, 2008 10:47 pm
Location: India

Re: 371 - Ackermann Functions #TLE. Please Help!

Post by theharshest » Wed Mar 11, 2009 10:02 pm

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);
	}
}
"if u r goin thru hell, keep goin"

redrumpeace
New poster
Posts: 3
Joined: Fri May 29, 2009 9:20 am

Re: 371 : Ackermann Functions :: TL

Post by redrumpeace » Fri May 29, 2009 9:32 am

Hello, desperate here.. It got TLE.. :o :( :cry:

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
New poster
Posts: 3
Joined: Fri May 29, 2009 9:20 am

Re: 371 - Anckerman Functions - Why TLE ?

Post by redrumpeace » Fri May 29, 2009 9:34 am

Hello, desperate here.. It got TLE.. :o :( :cry:

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 371 - Anckerman Functions - Why WA ?

Post by mf » Fri May 29, 2009 5:18 pm

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
New poster
Posts: 7
Joined: Fri Sep 18, 2009 5:15 pm
Location: Dhaka
Contact:

Re: 371 - Anckerman Functions - Why WA ?

Post by Azad Salam » Mon Oct 12, 2009 3:20 am

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
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 371 - Anckerman Functions - Why WA ?

Post by Jehad Uddin » Mon Oct 12, 2009 12:04 pm

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 ) :D

Azad Salam
New poster
Posts: 7
Joined: Fri Sep 18, 2009 5:15 pm
Location: Dhaka
Contact:

AC :D :D

Post by Azad Salam » Mon Oct 12, 2009 6:39 pm

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

etameem
New poster
Posts: 5
Joined: Tue Jul 21, 2009 11:11 am
Location: (CSE, JU) Dhaka,Bangladesh
Contact:

Re: 371"Ackermann Functions "

Post by etameem » Mon Nov 09, 2009 11:51 pm

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...

Post Reply

Return to “Volume 3 (300-399)”