371 - Ackermann Functions

[LithiumDex]

3. L can be >= H, is L is > H, swap L and H, in output print L and H in order.

[SARKAR]

how about .193 seconds

[gba356]

I've tried a lot of inputs without no incorrect outputs.
Can somebody give me some critical inputs or correct my code?
I appreciate that.

Code: Select all

Code removed after AC.
Missed the lines:
L = the lower boundary value in the sequence
H = the upper boundary value in the sequence 

Thanks for Rio's help!!

[rio]

Dear Aengus

Check these

1 2
Between 1 and 2, 1 generates the longest sequence of 3 values.
2 1
Between 1 and 2, 1 generates the longest sequence of 3 values.

From previous post.
----
Rio

[rudy yulianto]

i try your cases from Aengus..

Code: Select all

1 2
1 10000
30000 100000
1 1000000
2000000000 2001000000
1234567890 1235678901
0 0

i try input --> 1 10000
but that inputs changed in my code...

please some body check my code...

Code: Select all

#include<stdio.h>
#include<stdlib.h>

int main()
{   
	long long input[1000][2],temp;
	long long data[1000][2];
	long long i=-1,j,k,l,cad,bny,index;

	do
	{
		i++;
//test 1 case input--> 1 10000
		scanf("%I64d %I64d",&input[i][0],&input[i][1]); 
                                                                                
		if(input[i][0]>input[i][1])
		{
        	   temp = input[i][0];
	           input[i][0] = input[i][1];
        	   input[i][1] = temp;                           
	        }
	}while(input[i][0] != 0 && input[j][1] != 0);
    

    for(j=0 ;j<i ;j++)
	{
		index=0;

		for(l=0,k=input[j][0] ;k<=input[j][1] ;k++,l++)
		{
			cad = k;
			bny=0;
			do
			{

				if( cad%2 == 0 )
					cad/=2;
				else
					cad = (3*cad)+1;

				bny++;

				if(cad==1)
					break;

			}while(1);
			
			if(l!=0 && bny>data[index][0])
			{
				index = l;
			}
			data[l][0] = bny;
			data[l][1] = k;
		}
		//why change ?? --> input[0][0] = 1 , input[0][1] = 10000
		printf("Between %I64d and %I64d, %I64d generates the longest sequence of %I64d values.\n",input[j][0],input[j][1],data[index][1],data[index][0]);
	}
    system("pause");
	return 0;
}

sorry my english bad..
thx before..

[Jan]

The identifier for 'long long' is '%lld'. Is that your problem?

[mistycheney]

I got .160s~~ however I didn't pay much attention to the efficiency of algorithm when I'm writing the code~~~it's just lucky

[sapnil]

I get Acc in 0.42
I done this like problem no 100 (3n+1)

Thanks
Keep posting
Sapnil

[Obaida]

I got Accc. in 100 by this code. But what's up hear.. plzzzzzzz help me....

Code: Select all

#include<stdio.h>
int main()
{
	long long n,r,i,p,s,count,max,num;
	while(scanf("%lld %lld",&n,&p)==2)
	{
		if(n==0&&p==0)
		{
			break;
		}
		else
		{
			printf("Between %lld and %lld, ",n,p);
			if(n>p)
			{
				long long int t;
				t = n;
				n = p;
				p = t;
			}	
			max=0;
			for(i=n;i<=p;i++)
			{
				count=0;
				s = i;
				while(s!=1)
				{
					count = count + 1;
					r=s%2;
					if(r==1)
					s=3*s+1;
					else
					s=s/2;						
				}
				if(count>max)
				{
						max=count;
						num=i;
				}
			}

			printf("%lld generates the longest sequence of %lld values\n",num,max);
		}
			
	}
	return 0;
}

[Obaida]

Over come previous problem... now time limit on .652 it ok, but giving wrong answer.... plzzzzzzzzzz help me

[Obaida]

Over come previous problem... now time limit on .652 it ok, but giving wrong answer.... plzzzzzzzzzz help me

Code: Select all

#include<stdio.h>
int main()
{
long long int a,n,b,count,max,i,t,num,x[1000];
while(scanf("%lld %lld",&a,&b)==2)
{
	if(a==0&&b==0)
	{
		break;
	}
	else
	{
		printf("Between %lld and %lld, ",a,b);
		if(a>b)
		{
			t=b;
			b=a;
		}
		else
			t=a;
		max=0;
		for(i=t;i<=b;i++)
		{
			 count=0;
			 n=i;
			while(n!=1)
			{
				 if(n%2==1)
					n=3*n+1;
				else
					n=n/2;
				 count++;
			}
			if(count>=max)
			{
				num=i;
				max=count;
			}
		}
	       printf("%lld generates the longest sequence of %lld values.\n",num,max);
		}
	}
   return 0;
}

[mahedee]

Please help me. I found the TLE. Please help me to solve the problem.

Code: Select all

#include<stdio.h>

int main()
{
	long l,h,j,i,s,count,max,t;
	while(scanf("%ld %ld",&l,&h)==2)
	{
		max = 0;
		if(l==0&&h==0) break;
		if(l>h)
		{
			t = h;
			h = l;
			l = t;
		}
		for(j = l; j<=h; j++)
		{
			i = j;
			count = 0;
			while(i!=1)
			{
				if(i%2==0)
					i = i/2;
				else
					i = i*3+1;			
				count++;
				if(count>max)
				{
					max = count;
					s = j;
				}
				//if(i==1) break;
			}
		}

		printf("Between %ld and %ld, %ld generates the longest sequence of %ld values.\n",l,h,s,max);
	}
	return 0;
}

[andy0518]

I dont know the wrong of the code
I count 1 to 10000 first
if the input < 10000, I just use the len[input]

please tell me what is wrong
thank you very much

Code: Select all

#include<stdio.h>
#define MAX 10000
struct num
{
  unsigned int length;
  unsigned int value;
};
int len[MAX];
int ackermann(unsigned int n)
{
  unsigned int i,length=0;
  for(i=n,length=0; i!=1;length++)
  {
    if(i < MAX)
      return len[i];
    if(i%2 == 0)
      i = i/2;
    else
      i = 3*i+1;
  }
  return length;
}
void init()
{
  for(int i=0; i<MAX; i++)
    len[i] = 0;
  len[1] = 0;
  len[2] = 1;
  for(int i=3; i<MAX; i++)
  {
    int length=0;
    for(int j=i; j!=1; length++ )
    {
      if(j<MAX)
      {
        if(len[j] != 0)
        {
          len[i] = len[j] + length;
          break;
        }
      }
      if(j%2 == 0)
        j = j/2;
      else
        j = 3*j+1;
    }
    if(len[i] == 0)
      len[i] = length;
  }
}
int main()
{
  unsigned int L,H,tmp;
  unsigned int length;
  struct num max;
  scanf("%u %u",&L,&H);
  init();
  while(!(L==0 &&H==0))
  {
    if(L>H)
    {
      tmp = L;
      L = H;
      H = tmp;
    }
    max.length = 0;
    for(unsigned int i=L; i<=H; i++)
    {
      if(i%2 == 0)
        length = ackermann(i/2)+1;
      else
        length = ackermann(3*i+1)+1;
      if(length > max.length)
      {
        max.length = length;
        max.value = i;
      }
    }
    printf("Between %u and %u, %u generates the longest sequence of %u values.\n",L,H,max.value,max.length);
    scanf("%u %u",&L,&H);
  }
  return 0;
}

[Jan]

Search the board first. Use existing thread.

[Moshiur Rahman]

try to do some memoization.

Don't calculate for the same input again, just save the cycle length in an array...