## 371 - Ackermann Functions

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### ACM 371

The similar problem like this one I got accepted. But I can't get this problem accepted. Is there any tricky part of this problem?
[c]
#include<stdio.h>
#define SWAP(x,y,t) (t=x,x=y,y=t)
void main(void)
{
long long cycle,temp,i,j,t,a,b,record,max;
while(1)
{
scanf("%lld %lld",&i,&j);
if(i==0 && j==0)
break;
a=i,b=j;
if(a>b)
SWAP(a,b,t);
max=0;
for(;a<=b;a++)
{
temp=a;
cycle=1;
if(temp%2)
temp=temp*3+1;
else
temp/=2;
while(temp!=1)
{
if(temp%2)
temp=temp*3+1;
else if(temp%2==0)
temp/=2;
cycle++;
}
if(max<cycle)
{
max=cycle;
record=a;
}
}
printf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n",i,j,record,max);
}
}
[/c]

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
you have to swap i and j too when i>j

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
I got accepted. Thanks.

Daniel Chia
New poster
Posts: 12
Joined: Mon Jul 29, 2002 3:04 pm
Contact:

### Could someone look my code over and kindly tell me y WA?

[c]#include <stdio.h>

int main()
{
long l,h,v, i,e,t,c;
scanf("%ld %ld", &l,&h);

while((l != 0) && (h != 0))
{
if (l > h)
{
v = l;
l = h;
h = v;
}
v = 0;
for (i =l; i<=h; i++)
{
e = i;
t = 0;
do
{
if ( e % 2 ==0 ) e /= 2;
else e = e*3 +1;
t++;

} while ( e != 1);
if (t > v)
{
v = t;
c = i;
}
}
printf("Between %ld and %ld, %ld generates the longest sequence of %ld values.\n",l,h,c,v);
scanf("%ld %ld", &l,&h);
}

return 0;
}[/c]

MD. KHAIRULLAH
New poster
Posts: 1
Joined: Sat Aug 03, 2002 8:26 am

### why this program is not accepted ?

#include<stdio.h>
int cycle(unsigned long x)
{
int length=0;
unsigned long n;
n=x;
while(1)
{
length++;
if(n%2==0)
n/=2;
else
n=3*n+1;
if(n==1)
return length;
}
}
void main(){
int max,a,b,count,lower,upper;
int length,value;
while(scanf("%d%d",&a,&b)==2&&a!=EOF&&b!=EOF&&a!=0&&b!=0)
{
if(a>b)
{
upper=a;
lower=b;
}
else
{
upper=b;
lower=a;
}
value=0;
for(count=lower;count<=upper;count++)
{
length=cycle(count);
if(length>value)
{
max=count;
value=length;
}
}
printf("Between %d and %d, %d generates the longest sequence of %d values.\n",a,b,max,value);
}
}

monika
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am
You've not mentioned, which problem you are trying to solve.

If this is 100 ( The 3n+1 Problem ), then you should post it in Volume I.

Also, take care of the ouput format required by the problem description. You only need to print a, b and value.

MAXX^FACTOR
New poster
Posts: 7
Joined: Mon Sep 16, 2002 7:29 am
Location: EARTH.ASIA.TAIWAN.TAIPEI
Contact:

### OH CRAP!

your method is too slow .............and "TIMELIMITEXCEEDED" is happened

OH! CRAP~~~~~~

Daniel Chia
New poster
Posts: 12
Joined: Mon Jul 29, 2002 3:04 pm
Contact:

### I got AC

Actually, the method is sufficient for this problem. Although there is a faster method, which must be used in qn 100.
It turns out that certain points of the computation exceeds the capacity of long int

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
It does not exceed 4-byte integer... though it exceeds the size of the signed 4-byte integer. The answers and all intermediate values are less than 2^32.

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

### 371 time exceed

Is it possible to shorten the time?
This exceed the time limit.
Last edited by Eric on Sun Apr 20, 2003 11:53 am, edited 1 time in total.

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm
what's the fast algorithm to this problem?
I got TLE after rejudging.

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am
Ya it can be shorten.
As i use c++ i am putting a pseudocode here:

Code: Select all

``````Let the interval is i......j

max <-- 0

for i = i to j
do    s     <-- i
len <-- 1
while s not equal to 1
do   if   ( s is odd )
s <-- s / 2 + 1
len <-- len + 2      /*-Tricky PArt -*/
else
s  <-- s / 2
len <-- len + 1
if ( i = 1 )
len <-- 4
max <-- MAX ( max, len)
ans <-- i

print ( ans, max - 1 )
end loop

``````
Acual C code :

Code: Select all

``````#include<stdio.h>
unsigned long i,j,temp,n,len,s,ans,max,k,x;

int main(){
while(scanf("%lu%lu",&i,&j)==2){
if(!i&&!j)break;
max=0;
if(i>j)temp=i,i=j,j=temp;
printf("Between %lu and %lu, ",i,j);
for(;i<=j;i++){
for(s=i,len=1;s!=1;len++){
if(s%2) s+=s/2+1,len++;
else s/=2;
}
if(i==1)len=4;
if(len>max)max=len,ans=i;}
printf("%lu generates the longest sequence of %lu values.\n",ans,max-1);
}
return 0;
}
``````

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
I see your point and have modified my program
but it still gets time limit exceeded...
Last edited by Eric on Sun Apr 20, 2003 11:54 am, edited 1 time in total.

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:
This problem requires temporary values stored.
The optimization by Mahbub is very well.
But to solve it in 0.2 ~ 0.3 temporary values should be saved in
an array. The interval of judge inputs are not more than 400000.
So, a good way to solve this problem is having an array of 400000
elements. If one is then checking 10 -> 5,16,8,4,2 all has less sequence length than 10 , so they needs not to be checked.
moreover,after checking 10 if one stores the sequence length, he can
use it later as he somehow falls to 10 , ie:

_________________________________________popel

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am
Well Sending Table will certainly have faster run but i am really astonished why a time limit question arises:

As i resend my code today i get acc in .00.555 seconds. I think this is not bad.

Code: Select all

``````#include<stdio.h>
unsigned long i,j,temp,n,len,s,ans,max,k,x;

int main(){
while(scanf("%lu%lu",&i,&j)==2){
if(!i&&!j)break;
max=0;
if(i>j)temp=i,i=j,j=temp;
printf("Between %lu and %lu, ",i,j);

for(;i<=j;i++){
for(s=i,len=0;s!=1;len++){
if(s%2) s+=s/2+1,len++;
else s/=2;
}
if(i==1)len=3;
if(len>max)max=len,ans=i;}
printf("%lu generates the longest sequence of %lu values.\n",ans,max);
}
return 0;
}
``````
Thanks.
Light