371 - Ackermann Functions
Moderator: Board moderators
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]
[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]
-
- 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]
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]
-
- 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);
}
}
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);
}
}
-
- 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~~~~~~



OH! CRAP~~~~~~
-
- 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
It turns out that certain points of the computation exceeds the capacity of long int

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
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.
371 time exceed
Is it possible to shorten the time?
This exceed the time limit.
This exceed the time limit.
Last edited by Eric on Sun Apr 20, 2003 11:53 am, edited 1 time in total.
Ya it can be shorten.
As i use c++ i am putting a pseudocode here:
Acual C code :
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
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;
}
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:
....,3,10----(completed adding stored value)
....20,10---( completed adding stored value)
_________________________________________popel
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:
....,3,10----(completed adding stored value)
....20,10---( completed adding stored value)
_________________________________________popel
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.
Thanks.
Light
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;
}
Light