371 - Ackermann Functions

[yiuyuho]

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]

[/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]

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]

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]

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]

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]

[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]

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

[Hisoka]

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]

why ?

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

[Hisoka]

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]

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
input and show answer ).

3) Your algo is good.

Yo

[maurelio1234]

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

thanks in advance

[Aengus]

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]

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:

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