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

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

Post by LithiumDex »

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

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

Post by SARKAR »

how about :lol: .193 seconds

gba356
New poster
Posts: 15
Joined: Sat Apr 28, 2007 10:12 am
Location: Taiwan

Post by 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!!
:oops:
Last edited by gba356 on Mon Jun 18, 2007 1:42 pm, edited 1 time in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Re: check this input & output

Post by rio »

osan wrote: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
New poster
Posts: 4
Joined: Sun Sep 09, 2007 1:42 pm
Location: Indonesia
Contact:

try some cases from Aengus

Post by 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..
sorry my english is bad

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

The identifier for 'long long' is '%lld'. Is that your problem?
Ami ekhono shopno dekhi...
HomePage

mistycheney
New poster
Posts: 6
Joined: Sat Sep 29, 2007 11:11 am

how about .160s

Post by 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
Last edited by mistycheney on Fri Oct 12, 2007 7:25 am, edited 1 time in total.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil »

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

Thanks
Keep posting
Sapnil

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

TLE 371.....plzzzzzzz Help

Post by 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;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

no..... this shouldn't be....

Post by Obaida »

Over come previous problem... now time limit on .652 it ok, but giving wrong answer.... plzzzzzzzzzz help me
try_try_try_try_&&&_try@try.com
This may be the address of success.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

no..... this shouldn't be....

Post by 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;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

mahedee
New poster
Posts: 3
Joined: Sun Mar 23, 2008 1:29 pm
Contact:

371 - Ackermann Functions #TLE. Please Help!

Post by 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;
}
Mahedee

andy0518
New poster
Posts: 2
Joined: Wed Aug 20, 2008 5:21 pm

371 WA

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 371 WA

Post by Jan »

Search the board first. Use existing thread.
Ami ekhono shopno dekhi...
HomePage

Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm
Location: State University of Bangladesh

Re: 371 - Ackermann Functions #TLE. Please Help!

Post by Moshiur Rahman »

try to do some memoization.

Don't calculate for the same input again, just save the cycle length in an array...
Never think too hard, let ideas come to you...

Post Reply

Return to “Volume 3 (300-399)”