## 371 - Ackermann Functions

Moderator: Board moderators

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

### Re: 371 - Anckerman Functions - Why WA ?

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

### Re: 371 - Anckerman Functions - Why WA ?

@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 ?

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

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### 371 - Anckerman Functions - input limit ?

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

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

### Re: 371 - Anckerman Functions - Why WA ?

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.

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

Even after using memoization I am getting TLE... 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=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

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
New poster
Posts: 20
Joined: Thu Jan 17, 2008 10:47 pm
Location: India

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

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

### Re: 371 - Anckerman Functions - Why TLE ?

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

### Re: 371 - Anckerman Functions - Why WA ?

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

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

### Re: 371 - Anckerman Functions - Why WA ?

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

here is my code {in C}

#include<stdio.h>

int main()
{ long list,i,n,tmp,a,b,ans1,ans2;
list=0;
list=3;
list=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;
}

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 371 - Anckerman Functions - Why WA ?

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

### AC :D :D

Thnx jehad for ur help...now got ac :D  etameem
New poster
Posts: 5
Joined: Tue Jul 21, 2009 11:11 am
Contact:

### Re: 371"Ackermann Functions "

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;
}

``````