100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

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.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

problem with 3n+1, always wrong answer

Post by 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
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

wrong answer at 3n+1 problem (100)

Post by 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
Last edited by awik_10 on Sun May 18, 2003 1:31 pm, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by 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



P.S. I submitted a slightly modified version of your code and got ACC!!!!
Just a very minor mistake, really...... :D :D :D
Last edited by Observer on Sun May 18, 2003 12:36 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

Post by 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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by 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!!!! :lol: :lol:


Your program gives a correct answer for this:
1 2
But not for this:
1 2
1 2
Think about it..................
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

Post by awik_10 »

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

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

* Please delete your code by using the "Edit" function*
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

fpnc
System administrator
Posts: 201
Joined: Sun Oct 07, 2001 2:00 am
Location: Valladolid, Spain

If you get WA in problem 100, read me before post!

Post by 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.
Best regards,

Fernando N

powerboy
New poster
Posts: 8
Joined: Mon May 12, 2003 6:13 am
Contact:

problem 100

Post by 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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

yes, like that. end at EOF.

Crystal Vision Coders
New poster
Posts: 1
Joined: Fri May 23, 2003 11:58 am
Location: UK
Contact:

Post by 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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

try this input

Code: Select all

1 1
5 5
10 10
with love & light,

titid
Kalo mau kaya, buat apa sekolah?

Xeross
New poster
Posts: 2
Joined: Tue May 27, 2003 6:33 am

3n+1. Time Limit

Post by 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
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:

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

Post Reply

Return to “Volume 1 (100-199)”