100 - The 3n + 1 problem

[..]

You are making the most common mistake in problem 100. If you pay time and read other post about problem 100, you will know what is the mistake.

[awik_10]

i'm still a newbie, can anybody tell what's my wrong

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

int panjang(unsigned long a,unsigned long b)
{
int ctr=0,cycle=1,i;
unsigned long c,other_a,temp,x=1,y=1,k=1,l=1;
if(a>b)
{
c=a;
a=b;
b=c;
}
other_a=a;
while(other_a<=b)
{
ctr=1;
temp=other_a;
while(temp!=1)
{
ctr++;
/* if(temp%2==0)
{
if(x<temp) { x=temp; y=1; }
}
if(temp%2!=0)
{
if(k<temp) { k=temp; l=1; }
}
*/

if(temp%2!=0) { temp=temp*3+1; }
else{ temp=temp/2; }
if(temp==x&&temp!=1) { ctr=ctr+y-1; break; }
if(temp==k&&temp!=1) { ctr=ctr+l-1; break; }
}
cycle=cycle>=ctr?cycle:ctr;
if(ctr>y&&other_a%2==0)
{
x=other_a;
y=ctr;
}
if(ctr>l&&other_a%2!=0)
{
k=other_a;
l=ctr;
}
other_a++;
}
return cycle;
}

int main()
{
unsigned long a,b;
while(scanf("%lu%lu",&a,&b)==2)
{
if(a>0&&a<1000001&&b>0&&b<1000001)
printf("%lu %lu %d",a,b,panjang(a,b));
}
return 0;
}

it said that it ran during 4.189 seconds.

best regards,
awik

[awik_10]

i'm sorry about the previous one. can you tell me waht's my wrong? and it said that it ran during 4.189 seconds . this is my code with some of my explanations.

i wait for your replies. thank you.
best regards,

awik

[Observer]

Try to output your answer to a file (instead of on the screen).

If you still can't see the problem, tell me.



P.S. I submitted a slightly modified version of your code and got ACC!!!!
Just a very minor mistake, really......

[awik_10]

i still don't get it .
Try to output your answer to a file (instead of on the screen).
can you give me more explanation. by the way, thank you

awik

[Observer]

Well, sorry...... I'm not a C++ user...
(Can you use file input/output?)

Your problem comes from the layout of the output.
Don't you realize that there's something unnatural in your output format?

By adding just ONE line in your code, you can get an ACC!!!!


Your program gives a correct answer for this:

1 2

But not for this:

1 2
1 2

Think about it..................

[awik_10]

thank you anyway for your suggestion. i've just submitted it and got an acc. it only minus "\n" .
awik

[Observer]

Good for you! Glad that you find it out yourself!!!!!!!!!

* Please delete your code by using the "Edit" function*

[fpnc]

Please, read carefully the statement; in particular, do not asume that i < j.

If you have any other question about this problem 100, please use this thread. Thank you.

[powerboy]

The input for problem 100 is a series of lines of numbers.
How do i know when the input ends?
In addition, should i print all the output after all the input or
should i follow the format
input
output
input
output
etc...

[Hisoka]

yes, like that. end at EOF.

[Crystal Vision Coders]

Hi All,

I'm a newby to programming contests so be gentle with me. I have written what I think is a solution to problem 100. I submitted it and it got sent back with WA. Investigation suggested that for 113383 int was wrapping to -ve values so I changed to unsigned long but I still get WA. Now (on my PC) I can calculate answers for 1 to 1000000 in 2.5 sec and I use no arrays so the memory usage should be minimal. The examples that are given in the problem all give the correct answers and I have checked with the example code for the problem and can see no significant differences. Can anybody give me a hint as to where I am going wrong. (My code below).

Thanks in advance

Phil Mason

[c]
#include <stdio.h>

int main(void)
{
int start_val, stop_val, max_length, length;
int orig_start, orig_stop;
unsigned long temp, i;


while(scanf("%d %d\n",&start_val,&stop_val)==2)
{
max_length = 0;

/* Store Original order incase they get swapped */
orig_start = start_val;
orig_stop = stop_val;

/* Swap if needed */
if(start_val > stop_val)
{
stop_val = start_val;
start_val = orig_stop;
}

for(i=start_val; i<stop_val; i++)
{
/* reset the length */
length = 1;
/* Perform the initial calculation */
temp = i;
/* perform the loop */
while(temp != 1)
{
if(temp%2)
temp = (3*temp)+1;
else
temp = temp/2;
length++;
}
/* check that the length not longer than the max */
if(length > max_length)
max_length = length;
} /* End of the for loop */
printf("%d %d %d\n",orig_start, orig_stop, max_length);
}
return(1);
}

[/c]

[titid_gede]

try this input

Code: Select all

1 1
5 5
10 10

with love & light,

titid

[Xeross]

I tried in brute force, so I get TL.

So I collected all of method about solution, constant and cache.

But I am get the message, TL, continouly -_-;;

What the hell is the problem in the source below?

Thanks for reading.

------

#include <stdio.h>

#define MAXNUM 100000

int g_stack[MAXNUM] = {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<=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;
}

printf( "%ld %ld %ld\n", nFrom, nTo, nMaxCount );
}
}

return 0;
}

[ayaw]

Hope this'll help u

Code: Select all

#include <stdio.h> 

#define MAXNUM 100000 

int g_stack[MAXNUM] = {0,}; 

int main(int argc, char* argv[]) 
{ 
	while( 1 )  

/* <--- Forever loops!! I can't find "return" for this function or "break" for this loops */

	{ 
		long int nFrom, nTo; 

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

			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; 
			} 

			printf( "%ld %ld %ld\n", nFrom, nTo, nMaxCount ); 
		} 
	} 

	return 0; 
}