371 - Ackermann Functions

[htl]

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]

you have to swap i and j too when i>j

[htl]

I got accepted. Thanks.

[Daniel Chia]

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

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

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]

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

OH! CRAP~~~~~~

[Daniel Chia]

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]

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

[Eric]

Is it possible to shorten the time?
This exceed the time limit.

[lowai]

what's the fast algorithm to this problem?
I got TLE after rejudging.

[Mahbub]

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]

I see your point and have modified my program
but it still gets time limit exceeded...

[popel]

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

[Mahbub]

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