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

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

ACM 371

Post by htl » Tue Jul 02, 2002 6:35 pm

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:

Post by Picard » Tue Jul 02, 2002 7:10 pm

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

Post by htl » Wed Jul 03, 2002 5:00 am

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?

Post by Daniel Chia » Wed Jul 31, 2002 4:37 pm

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

Post by MD. KHAIRULLAH » Sat Aug 03, 2002 8:40 am

#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

Post by monika » Wed Aug 07, 2002 6:29 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.

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

OH CRAP!

Post by MAXX^FACTOR » Mon Sep 30, 2002 2:21 pm

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

OH! CRAP~~~~~~

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

I got AC

Post by Daniel Chia » Mon Sep 30, 2002 3:05 pm

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

Post by Ivor » Mon Sep 30, 2002 3:28 pm

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

Post by Eric » Thu Oct 24, 2002 3:29 pm

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

Post by lowai » Sun Nov 03, 2002 6:50 am

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

Post by Mahbub » Wed Nov 06, 2002 5:59 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

Post by Eric » Sat Nov 09, 2002 5:07 am

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
Location: Dhaka, Bangladesh
Contact:

Post by popel » Mon Nov 18, 2002 11:09 am

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
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

Post by Mahbub » Mon Nov 18, 2002 2:05 pm

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

Post Reply

Return to “Volume 3 (300-399)”