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

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

Re: something wrong:

Post by yiuyuho » Fri Mar 07, 2003 9:36 pm

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 "

Post by SilVer DirectXer » Mon Apr 07, 2003 6:07 am

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Apr 07, 2003 12:19 pm

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

Post by 29145 » Mon Apr 07, 2003 2:24 pm

some one please help me too its givin wa.... :cry:
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]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Apr 08, 2003 7:21 am

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.

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

Post by szymcio2001 » Mon Apr 21, 2003 12:16 pm

29145 wrote:some one please help me too its givin wa.... :cry:
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.

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

Re: 371"Ackermann Functions "

Post by szymcio2001 » Mon Apr 21, 2003 12:19 pm

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

Post by Almost Human » Wed Apr 30, 2003 6:22 am

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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Wed Apr 30, 2003 8:20 am

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

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

Post by Almost Human » Wed Apr 30, 2003 9:33 am

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

Post by Hisoka » Wed Apr 30, 2003 3:53 pm

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:

Post by globi » Mon May 05, 2003 11:01 am

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
New poster
Posts: 3
Joined: Sat Sep 13, 2003 5:31 pm
Location: Brazil
Contact:

Post by maurelio1234 » Wed Oct 29, 2003 10:13 pm

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
New poster
Posts: 12
Joined: Thu Oct 30, 2003 1:38 pm
Location: St. Petersburg, Russia
Contact:

Continous problems with this problem

Post by Aengus » Thu Oct 30, 2003 1:45 pm

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:

Post by maurelio1234 » Thu Oct 30, 2003 3:01 pm

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 8)
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

Post Reply

Return to “Volume 3 (300-399)”