100 - The 3n + 1 problem

[yogeshgo05]

hey guys this is code , acm judge says TLE ,
some body tell me whats wrong , i m a begginer

# include <stdio.h>

int main()
{
int i,j,c=1;
int m,n,k=0,r;
printf("enter the value of i &j");
while(scanf("%d %d",&i,&j)!=EOF)
{
m=i,n=j;
r=i;
while(r!=j)
{ i=r;
c=1;
while(i!=1)
{

if((i%2)!=0)
{
i=3*i+1;

}
else
{
i=i/2;

}

c++;
}
if(k<c)k=c;
r++;

}
printf("%d %d %d ",m,n,k);



}
return 0;
}

[Timo]

Hi yogeshgo05,

your code is little wrong.
you must to set the value of k to zero when read a new input.

your code is TLE because the first input can be greater than the second input.
your code didn't handle that case so it loop forever.

I have fixed your code and send it to judge and get AC.
here is your fixed code

Code: Select all

#include <stdio.h>

void swap(int *a, int *b)
{
	int c;
	c=*a;
	*a=*b;
	*b=c;
}

int main()
{

	int i,j,c=1;
	int m,n,k=0,r;

	while(scanf("%d %d",&i,&j)!=EOF)
	{
		m=i,n=j;
		if(i>j) swap(&i,&j);
		r=i;
		
		k=0;
		while(r!=j+1)
		{ 
			i=r;
			c=1; 
			while(i!=1)
			{
				if((i%2)!=0)
				{
					i=3*i+1;
				}
				else
				{
					i=i/2;
				}
				c++;
			}
			if(k<c)k=c;
			r++;
		}
		printf("%d %d %d\n",m,n,k);



	}
	return 0;
}

[ayon]

printf("enter the value of i &j");

please dont print anything unwanted, otherwise u'll get wrong answer. and post topic at the right place. this topics might be posted at volume I, with the subject including both problem number and problem name, moreover better use code tag, so that your code will be easily readable(as Timo did), have a nice day

[Dewr]

i updated my program! i want speed!
judge server said me "RUNTIME ERROR!"

Code: Select all

#include <stdio.h>
#include <memory.h>
#ifndef ONLINE_JUDGE
#include <time.h>
clock_t start, finish;
#endif

unsigned int inputi;
unsigned int inputj;
unsigned int cycle;
unsigned int nownumber;
unsigned int maxcycle;
unsigned int thenumber;
unsigned int dummy;
unsigned int boolsw = 0;
unsigned int * data;

void checkitup();
unsigned int checkit();

int main()
{
    data = new unsigned int[1000000];
    memset(data, 0, 4000000);
    lalala:
    maxcycle = 1;
    
    if(scanf("%u %u", &inputi, &inputj)==EOF)
    {
       delete[] data; 
       return 0;
    }
    
    #ifndef ONLINE_JUDGE
    if(inputi<1 || inputi >999999 || inputj<1 || inputj >999999)
    {
      printf("min = 1      max = 999999\n");
      goto lalala;
    }
    #endif
    
    #ifndef ONLINE_JUDGE
    start =clock();
    #endif
    if(inputi > inputj)
    {
         boolsw^=1;
         inputi^=inputj;
         inputj^=inputi;
         inputi^=inputj;
    }
    nownumber = inputi; 
    checkitup();
    
    do{
             nownumber++;
             if(checkit())
               continue;
             checkitup();
             }while(nownumber!=inputj);
    #ifndef ONLINE_JUDGE
    finish = clock();
    printf("it takes %f seconds.\n", (double)(finish-start)/(double)CLK_TCK);
    #endif
    
    if(boolsw)
    {
         boolsw^=1;
         inputi^=inputj;
         inputj^=inputi;
         inputi^=inputj;
    }
    printf("%u %u %u\n", inputi, inputj, maxcycle);
    goto lalala;
}

void checkitup()
{
	if(data[nownumber])
	{
		if(maxcycle<data[nownumber])
			maxcycle = data[nownumber];
		return;
	}
	   thenumber = nownumber;
       cycle = 0;
       while(1)
       {
             cycle++;
             if(thenumber == 1)
               break;
             else if(thenumber&1)  
             {
                  thenumber += (thenumber << 1);
                  thenumber++;
             }
             else
             {
				 dummy = thenumber>>1;
				 if(dummy < 1000000 && data[dummy])
                 {
                     cycle += data[dummy];
                     break;
                 }
                 thenumber>>=1;
             }
       }       
       data[nownumber] = cycle;
       if(maxcycle < cycle)
         maxcycle = cycle;
}

unsigned int checkit()
{
     dummy = nownumber<<1;
     if(dummy<=inputj)
       return 1;
     else
       return 0;
}

[mamun]

i updated my program! i want speed!
judge server said me "RUNTIME ERROR!"

Where did you update your program? Runtime error doesn't mean your program is running slow. You'll get Time limit exceeded for that.

[=viki=]

check out my prog its in C....im getting compile error prob 100

Code: Select all

#include<stdio.h>


long max=0;
void process(long,long);

int main(void)
	{
     long x,y;
     scanf("%d%d",&x,&y);
     process(x,y);
     printf("%ld  %ld  %ld\n",x,y,max);
     return 0;
 	}


void process(long x, long y)
	{long i,count=0,n;
	 for(i=x;i<y;i++)
		{
		 n=i;
		 while(1)
		       {
			count++;
			if(max<count)
				max=count;
			if(n==1)
			       {
				count=0;
				break;
			       }

			if((n%2)==0)
				n=n/2;

			else
				n=(3*n)+1;

		       }
		}
	}

using dev c++ for compilation...
its compiled on my system
whats the problem here?

[mamun]

Are you sure you're getting compile error?

[chunyi81]

I have been getting weird compile errors for C code myself for problem 142 which I wrote around one year ago and resubmitted as C code after some corrections and got compile error. The original code had compiled ok in the OJ when I submitted one year ago as C code as well. I had to submit my C code as C++ code to make it compile. I was not able to find out why my C code had compile error when I resubmitted because the e-mail address in my user profile for the OJ is gone and I could not edit my profile to enable it back.

From viki's code for problem 100, I think it might be because of this:

Code: Select all

long i,count=0,n;

Rewriting this as:

Code: Select all

long i,count,n;
count = 0;

might help.

Also your code will get WA from the judge even if you managed to get the judge to compile your code successfully.

There was something similar in my problem 142 code as well which could have caused the compile error in the OJ although it compiled fine with a gcc 2.95 compiler I have. Your code compiles fine with the gcc 2.95 compiler I have.

Also, you could enable the option in your profile to receive compile error messages via e-mail.

[tobby]

Also, you could enable the option in your profile to receive compile error messages via e-mail.

I don't think you can do that now, because the update info feature is not working.

[=viki=]

here goes the code

Code: Select all

#include<stdio.h>


long max=0;
void process(long,long);

int main(void)
	{
         long x,y;
         scanf("%ld%ld",&x,&y);
         process(x,y);
         printf("%ld  %ld  %ld\n",x,y,max);
         max=0;
         return 0;
 	}


void process(long x, long y)
	{long i,count=0,n;
	 for(i=x;i<y;i++)
		{
		 n=i;
		 while(1)
		       {
			count++;
			if(max<count)
				max=count;
			if(n==1)
			       {
				count=0;
				break;
			       }

			if((n%2)==0)
				n=n/2;

			else
				n=(3*n)+1;

		       }
		}
	}

im getting WA .. plz point out the problem here ..
this is m first ACM problem..
tried the while loop variation for taking input also
while(scanf("%d%d",&x,&)==2)
what shall i do plz help its working on m sstem for all inputs
plz help

[=viki=]

Code: Select all

#include<stdio.h>


long max=0;
void process(long,long);

int main(void)
	{
         long x,y;
         scanf("%ld%ld",&x,&y);
         process(x,y);
         printf("%ld  %ld  %ld\n",x,y,max);
         max=0;
         return 0;
 	}


void process(long x, long y)
	{long i,count=0,n;
	 for(i=x;i<y;i++)
		{
		 n=i;
		 while(1)
		       {
			count++;
			if(max<count)
				max=count;
			if(n==1)
			       {
				count=0;
				break;
			       }

			if((n%2)==0)
				n=n/2;

			else
				n=(3*n)+1;

		       }
		}
	}

plz help now im getting WA whats wrong here plz point out

this is my first ACM problem
so if some thing is wrong in taking input plz point out...

[Emilio]

The input haven't only a case.
You must check if x is greater than y or not.
By other hand, you must reuse another post that talk about the same problem, also there are a lot of post about this problem that you can have a look and I'm almost sure that they will resolve your doubts and mistakes.
Good luck!

[=viki=]

Code: Select all

#include<stdio.h>


long max=0;
void process(long,long);

int main(void)
	{
         long x,y;
         scanf("%ld%ld",&x,&y);
         process(x,y);
         printf("%ld  %ld  %ld\n",x,y,max);
         max=0;
         return 0;
 	}


void process(long x, long y)
	{long i,count=0,n;
	 for(i=x;i<y;i++)
		{
		 n=i;
		 while(1)
		       {
			count++;
			if(max<count)
				max=count;
			if(n==1)
			       {
				count=0;
				break;
			       }

			if((n%2)==0)
				n=n/2;

			else
				n=(3*n)+1;

		       }
		}
	}

plz sm1 compile n run this code on ur system n tell me whats wrong gettin WA... but its running on my system (using dev c++)...
this is my first ACM problem ..heavent submitted any prob before
tried to submit it more than 10 times .. initially it was CE now im getting WA plz help

[=viki=]

e i tried....

Code: Select all

#include<stdio.h>


long max=0;
void process(long,long);

int main(void)
	{
         long x,y;
         while(scanf("%ld%ld",&x,&y)==2) {
         process(x,y);
         printf("%ld  %ld  %ld\n",x,y,max);
         max=0;
         }
         return 0;
 	}


void process(long x, long y)
	{long i,count=0,n;
	 for(i=x;i<y;i++)
		{
		 n=i;
		 while(1)
		       {
			count++;
			if(max<count)
				max=count;
			if(n==1)
			       {
				count=0;
				break;
			       }

			if((n%2)==0)
				n=n/2;

			else
				n=(3*n)+1;

		       }
		}
	}

plz tell me whats the prob..
after while(scanf("%d%d",&x,&)==2) the loop never terminates

[tan_Yui]

plz sm1 compile n run this code on ur system n tell me whats wrong gettin WA... but its running on my system (using dev c++)...
this is my first ACM problem ..heavent submitted any prob before
tried to submit it more than 10 times .. initially it was CE now im getting WA plz help

Read my previous post in this thread.