100 - The 3n + 1 problem

[Xeross]

Yeah, it's my falut like little boy.
But I have problems yet. I met WA at this time.

Hope this'll help u

Code: Select all

#include <stdio.h>

#define MAXNUM 100000

int g_stack[MAXNUM] = {0,};
int g_swap = 0;

int main(int argc, char* argv[])
{
	while( 1 )
	{
		long int nFrom, nTo;

		while( 2 == scanf( "%ld %ld", &nFrom, &nTo ) )
		{
			int nMaxCount = 0;
			long int n;

			if( nFrom > nTo )
			{
				long int temp;
				temp = nTo;
				nTo = nFrom;
				nFrom = temp;
				g_swap = 1;
			}

			if (nFrom<=837799 && nTo>=837799) 
		    { 
				printf("%ld %ld %d\n",nFrom,nTo,525); 
				continue; 
			} 
			if (nFrom<=626331 && nTo>=626331) 
			{ 
				printf("%ld %ld %d\n",nFrom,nTo,509); 
				continue; 
			} 
			if (nTo<626331 && nFrom<=511935 && nTo>=511935) 
			{ 
				printf("%ld %ld %d\n",nFrom,nTo,470); 
				continue; 
			} 
			if (nTo<511935 && nFrom<=410011 && nTo>=410011) 
			{ 
				printf("%ld %ld %d\n",nFrom,nTo,449); 
				continue; 
			} 
			if (nTo<410011 && nFrom<=230631 && nTo>=230631) 
			{ 
				printf("%ld %ld %d\n",nFrom,nTo,443); 
				continue; 
			} 

			for( n = nFrom ; n <= nTo ; n++ )
			{
				long int nValue = n;
				int nCount = 0;

				while( 1 )
				{
					nCount++;

					if( 1 == nValue ) 
						break;
					else 
					{
						if( nValue<MAXNUM && (g_stack[nValue] != 0) )
						{
							nCount += g_stack[nValue]-1;

							break;
						}
						else
						{
							if( nValue & 1 )
								nValue = nValue * 3 +1;
							else
								nValue >>= 1;
						}
					}
				}
				
				if( nMaxCount < nCount )
					nMaxCount = nCount;

				if( n<MAXNUM && (g_stack[n] == 0) )
					g_stack[n] = nCount;
			}

			if( g_swap )
				printf( "%ld %ld %ld\n", nTo, nFrom, nMaxCount );
			else
				printf( "%ld %ld %ld\n", nFrom, nTo, nMaxCount );
		}
		
		break;
	}

	return 0;
}

I used swap, and change the value of variable and the sequence of output
Why do I have problem?

and one more question.
How do experts know the range of constants?
For example,
if (nFrom<=837799 && nTo>=837799)
printf("%ld %ld %d\n",nFrom,nTo,525);

[Diskerr]

It is just a trick to maximize speed.

Between 1 and 1000000, 837799 gives the longest sequence of 525.

So, if the pair (nFrom, nTo) includes 837799, answer is clearly 525, and we need not do any calculations.

This problem is very easy to solve. But unless you think with care, you will got WA.

Consider all of possible situations.

[ec3_limz]

This problem is very easy to solve. But unless you think with care, you will got WA.

This problem is indeed one of the easiest in the Online Judge problem set. Just using brute force is fast enough. The only trap I know of is that i need not be less than j.

[raihan]

I have used the all the options like not to think that 1st one is big but I still have the problem... furthur tips

[technogeek]

I tried to solve the first problem and it runs fine on my computer Win200, Bloodshed Dev C++ without errors. But the online judge says compile error.

01624693_24.c:38: syntax error before `!'

. What the hell is wrong ?

Code: Select all

/*   @JUDGE_ID:   xxxxxxx   100   C++ */
#include <stdio.h>

long int cycle,biggest;

void findlength(long int n)
{
 cycle++;

 if(n==1) return;

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

 findlength(n);

 if(cycle>biggest) biggest=cycle;
}

int main()
{
      long int i,j;
      while(1)
      {
       biggest=0;
       scanf("%ld %ld",&i,&j);
       for(int k=i;k<=j;k++)
       {
        cycle=0;
        findlength(k);
       }
       printf("%ld %ld %ld",i,j,biggest);
      }
      return 0;
}

[rjhadley]

The judge uses gcc and ANSI mode. You need to declare all variables before any actual code.

$ gcc -ansi -Wall -o 100 100.c
100.c: In function `main':
100.c:27: parse error before `int'
100.c:27: `k' undeclared (first use in this function)
100.c:27: (Each undeclared identifier is reported only once
100.c:27: for each function it appears in.)
100.c:27: warning: statement with no effect
100.c:27: parse error before `)'
100.c: At top level:
100.c:34: parse error before `return'

I'm not sure why you didn't get a reasonable list of compile errors back from the judge though...

[technogeek]

Oh hell........my mailer yahoo kept adding lines at the end. I included the @end_of_source_code and it compiles now. Thanks for your attention.

[Master]

your code is very clumgy.
try to solve it simply.
remember ":

simple is smart.

[ivec]

You probably should look for a problem elsewhere.

Have you considered inputs such as:
5 8
8 5
?


hth,
Ivan

[r.z.]

I always get WA......

I don't know why....

I've already tested it and there's no problem....

maybe you can help me?

[c]#include<stdio.h>

long int jumlah(long int n);

void main()
{ long int n1,n2,i,sum=0;
scanf("%li %li",&n1,&n2);
for(i=n1+1;i<n2;i++)
{ if(sum<jumlah(i))
sum=jumlah(i);
}
printf("%li %li %li",n1,n2,sum);
}

long int jumlah(long int n)
{ long int i=0;
while(n!=1)
{ i++;
if(n%2)
{ n=3*n+1;
}
else
n=n/2;
}
i+=1;
return i;
}[/c]

[Hisoka]

hello R.Z.....

first I saw your code you have a problem in I/O, range, and a little trick input :

Code: Select all

void main()
{   long int n1,n2,i,sum=0;
   scanf("%li %li",&n1,&n2);
   for(i=n1+1;i<n2;i++)
   {   if(sum<jumlah(i))
      sum=jumlah(i);
   }
   printf("%li %li %li",n1,n2,sum);
}

use this for input

Code: Select all

while(scanf("%li %li",&n1,&n2)==2)
{
  ...
}

because end of input is EOF.

after that if n1>n2 you must swap them, but in your output you must print like your input.

after that for this problem range of data is from n1 to n2

Code: Select all

for(i=n1;i<=n2;i++)

and for output you must print end of line

Code: Select all

printf("%li %li %li\n",n1,n2,sum);

I think that's all.

just for know, if you use:

Code: Select all

if(sum<jumlah(i)) sum=jumlah(i);

you will count cycle lenght twice, and this will waste your time limit.

GOOD LUCK.... (mr nice guy) ???

[r.z.]

thanks man!

I thoght the word between means n1<x<n2

ok thanks again!

[r.z.]

[c]
#include<stdio.h>

long int jumlah(long int n);

void main()
{ long int n1,n2,n3,n4,i,j=0,sum=0;
while(scanf("%li %li",&n1,&n2)==2)
{
if(n1>n2)
{ n3=n2;
n4=n1;
}
else
{ n3=n1;
n4=n2;
}
for(i=n3;i<=n4;i++)
{ j=jumlah(i);
if(sum<j)
sum=j;
}
printf("%li %li %li\n",n1,n2,sum);
}
}

long int jumlah(long int n)
{ long int i=0;
while(n!=1)
{ i++;
if(n%2)
{ n=3*n+1;
}
else
n=n/2;
}
i+=1;
return i;
}
[/c]

still not accepted.....
I don't know why this time....
I already tried your way....

[Max108]

I tested the problem with the code that you gave:

the only thing, the one that gives you wrong answer, is that you are not uptadating the maximum length to zero again... look try with this example.

100 200 = 125 //this is the correct answer
201 210 = 89 //same

but your program keeps giving 125 when it should give 89, i think thats the only bug you have there

[Zhao Le]

I think it should use read all input then write all output.

Because i use read one output one, get WA,

then changed got AC.

Who knows why, so I just wanna know.

I have meet this several times, I think is the <BUG>.