371  Ackermann Functions
Moderator: Board moderators
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>(L1)/3
so, if n>(L1)/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.
if it is odd, the n=3n+1, but we also have a limit L,
if 3n+1>L
then n>(L1)/3
so, if n>(L1)/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.

 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]
#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]
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=ab;
a=ab;
}
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]
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=ab;
a=ab;
}
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]

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

 New poster
 Posts: 38
 Joined: Mon Dec 09, 2002 1:53 pm
 Location: Poznan, Poland
Re: 371"Ackermann Functions "
You should write:SilVer DirectXer wrote: [cpp]cout<<"Between "<<input1<<" and "<<input2<<", "<<pos<<" generates the longest sequence of "<<max<<" values."<<endl;[/cpp]
[cpp]
cout << "Between " << smaller << " and " << bigger << (...);
[/cpp]

 Learning poster
 Posts: 93
 Joined: Sun Jan 12, 2003 3:30 pm
371  Ackermann Functions
This is my code , please help :
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 ;
}

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

 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:
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:
thanks in advance
is true... I used unsigned int and it was ok..."The largest value in the sequence will not be larger than can be accomodated in a 32bit Pascal LongInt or C long."
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:
and you cannot precalculate all answers because you don't know the range os the inputs...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.
thanks in advance

 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 longarithmetic 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, ..., H1, H, or L, L+1, ..., H1, or L+1, ..., H1?
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:
output:
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, ..., H1, H, or L, L+1, ..., H1, or L+1, ..., H1?
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
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.

 New poster
 Posts: 3
 Joined: Sat Sep 13, 2003 5:31 pm
 Location: Brazil
 Contact:
your aswers:
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:
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:
ps: I didn't put the other answers because my program ran into an infinite loopBetween 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.
.:. Marcos Aur