## 371 - Ackermann Functions

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### Re: something wrong:

The part for this problem will be this:

if it is odd, the n=3n+1, but we also have a limit L,
if 3n+1>L
then n>(L-1)/3

so, if n>(L-1)/3, then you sahould quit, this way you restrict all values in operation to be small enough to be stored as integers.

double will work also.

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

### 371"Ackermann Functions "

[/cpp]
#include <iostream>
#include <stdlib.h>
using namespace std;

long long int input1,input2,max,bigger,smaller,i,x,y,pos;

void main(void)
{
while (1)
{
cin>>input1>>input2;
if (input1==0 && input2==0)
exit(0);

bigger=input2;
smaller=input1;

if (input2<input1)
{
smaller=input2;
bigger=input1;
}

pos=1;
max=0;
for (i=smaller;i<=bigger;i++)
{ x=0;
y=i;
if (i>0)
while (1)
{
x++;
if (y % 2==0)
y/=2;
else
y=3*y+1;
if (y==1)
break;
}
if (x>max)
{
pos=i;
max=x;
}

}

cout<<"Between "<<input1<<" and "<<input2<<", "<<pos<<" generates the longest sequence of "<<max<<" values."<<endl;
}

}

[cpp]

i got a WA, anyone tell me what's wrong?[/cpp]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I think it may be useful to conver the following line:

y=3*y+1;

you see it will always generate an even number, so by dividing it by 2,
u get (3*n)/2 + 1/2.

now, since we will lose a 1 because of integer division, it is appropriate to write :
(3*n)/2 + 1

e.g (3*5+1)/2=8
but (3*5)/2 +1/2=7 29145
New poster
Posts: 3
Joined: Sun Mar 09, 2003 10:29 am
Location: india
some one please help me too its givin wa.... i didnt understand how to replace 3*n +1 to (3*n)/2+1 will it not affect the cycle length.....

[cpp]#include<iostream.h>
#include<math.h>

int cycle(double n)
{
int len = 0;
while(n!=1)
{
n = (fmod (n,2))? (3*n+1):n/2;
len ++;
}
return len;
}

void main()
{
double a,b,p;
int temp,max = 0;
while(cin>>a>>b)
{
max = 0; p=0;
if(a>b)
{
a=a+b;
b=a-b;
a=a-b;
}

if(a==0 && b==0)
break;
for(double i = a; i<=b;i++)
{
temp = cycle(i);
if (max < temp)
{
max = temp;
p = i;
}
}
cout<<"between "<<a<<" and "<<b<<", "<<p;
cout<<" generates the longest sequence of "<<max<<" values\n";
}
}
[/cpp]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
well consider this:

let n be 5 and suppose your cycle length is currently 11,

if you convert it to ( 3*5)/2 +1,
it is same as 3*5+1=16 and 16/2=8;
so your cycle length should be increased to 11+2=13.

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland
29145 wrote:some one please help me too its givin wa.... i didnt understand how to replace 3*n +1 to (3*n)/2+1 will it not affect the cycle length.....
I think that you don't consider that for 1 the length of the cycle is 3 and your output doesn't seem to be exactly identical as sample output.

szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

### Re: 371"Ackermann Functions "

SilVer DirectXer wrote: [cpp]cout<<"Between "<<input1<<" and "<<input2<<", "<<pos<<" generates the longest sequence of "<<max<<" values."<<endl;[/cpp]
You should write:
[cpp]
cout << "Between " << smaller << " and " << bigger << (...);
[/cpp]

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

### 371 - Ackermann Functions

Code: Select all

``````#include <stdio.h>

int main ( )
{
unsigned long result , counter , x , temp , tempmax , i , j ;

/*  freopen ( "371.in" , "r" , stdin ) ;
freopen ( "371.out" , "w" , stdout ) ;*/

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

printf ( "Between %lu and %lu, " , i , j ) ;

if ( i > j ) i ^= j ^= i ^= j ;

for ( x = i , result = 0 ; x <= j ; x++ )
{
counter = 0 ;
temp = x ;

do
{
if ( temp % 2 == 0 ) temp = temp / 2 ;
else temp = 3 * temp + 1 ;
counter ++ ;
}
while ( temp != 1 ) ;

if ( counter > result ) result = counter , tempmax = x ;
}
printf ( "%lu generates the longest sequence of %lu values.\n" , tempmax , result ) ;
}
return 0 ;
}
``````

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
hello......

I am not check your algo, but if you think your algo is right, you cannot use unsigned long for this problem, try to use double for temp variable, because temp can greater than 2^32. Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
why ?

it said that we can use C long for the input ...

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
yeah.... but it is only for input, but if the input is 2345678901, when this is a odd number under 2^32, so temp=3*temp+1, and this is greater than 2^32. for this you got WA, because if you use unsigned long you get negative result.

globi
New poster
Posts: 15
Joined: Wed Apr 23, 2003 2:44 pm
Location: Warsaw
Contact:
1) I think you should better use "long long" ( 64bit integer ) than double.
It will make less problems.

2) Use precalculation ( first count everything into to table, later read

Yo

maurelio1234
New poster
Posts: 3
Joined: Sat Sep 13, 2003 5:31 pm
Location: Brazil
Contact:
I got AC in this question right now and the phrase:
"The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long."
is true... I used unsigned int and it was ok...

ps: how can i optimize this program? i calculated it using a recursive function and a map for remembering the solutions i've already calculated and my solution ran in 5.316s... (there are some answers in 0.010 s at the ranking...)

i think there's no formula 'cause the problem says:
An Ackermann function has the characteristic that the length of the sequence of numbers generated by the function cannot be computed directly from the input value.
and you cannot precalculate all answers because you don't know the range os the inputs...

Aengus
New poster
Posts: 12
Joined: Thu Oct 30, 2003 1:38 pm
Location: St. Petersburg, Russia
Contact:

### Continous problems with this problem

I've already spent plenty of time on this problem and I am really curious where do I have mistakes. I've used the function for calculation that I already succesfully used in the problem 694 together with the long-arithmetic engine that I also used in several other problems.

So, my questions:

1. Can L (the first boundary) be greater than H (the second boundary). If it can, how this should be handeled? Should they be swapped or should it be treated as an empty interval? What should be outputed in case of empty interval?

2. Does the interval include its boundaries, e. g. if the boundaries are L, H, then what is the right sequence: L, L+1, ..., H-1, H, or L, L+1, ..., H-1, or L+1, ..., H-1?

3. Is it possible that L=0 and H>0? If so, how should 0 be handeled?

4. Hope, no negative integers in the input, cause I input values as unsigned long.

5. What is the length of series starting with 1: 3 or 0?

6. Are there any strict checks for the output format, such as the presence or absence of '\n' in the end of the last line?

7. Could anybody check these test cases:

input:

Code: Select all

``````1 2
1 10000
30000 100000
1 1000000
2000000000 2001000000
1234567890 1235678901
0 0``````
output:

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

maurelio1234
New poster
Posts: 3
Joined: Sat Sep 13, 2003 5:31 pm
Location: Brazil
Contact:

1. i don't know, but i treated this case, so if (L>H) swap(L,H)
2. yes
3. no
4. i used unsigned int, so if there were any negative inputs... Wrong Answer...
5. the length is 3 6. i don't know
7. I think these inputs are not valid... the specification says that no element in any sequence is bigger than 2^32... but 1235678901 will generate numbers bigger than 2^32...

the output of my AC code was:
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.
ps: I didn't put the other answers because my program ran into an infinite loop
.:. Marcos Aur