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

Post Reply
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 »

My input file was
1 10
100 200
201 210

and the output came as

1 10 20
100 200 125
201 210 89
201 210 89

the 3rd line gets continuosly printed.

I had modified my prog as

main()
{ int t,i,j,len;
for(t=1;;t++)
{
scanf("%d",&i);
if(i == 0 )
exit(1);
scanf("%d",&j);
printf(" %3d %3d %3d\n",i,j,maxlenij(i,j) );
}/* END of FOR */
}

So it appears that that after the last input line my prog fails to understand that it has to terminate.

Please help me out.
Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

how hard can be to read in two values?

[c]
while (scanf("%d%d", &i, &j) == 2)
{
/* your code here */
}
[/c]

in your case, you're checking the wrong return value.

Ivor

P.S. And you don't need %3d when printing numbers. See sample output.
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 »

This time my program worked properly in my computer but the judge replied WRONG ANSWER

Please run my prog on your computer and test it and tell me what to do(I really can't find any fault):

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

int maxlenij(int i,int j);/* gives maximum cycle
length for integers between and including i and j */
int len(int u);


main()
{ int t,i,j,len;

while (scanf("%d%d", &i, &j) == 2)
{
printf(" %3d %3d %3d\n",i,j,maxlenij(i,j) );
}/* END of WHILE */

}

int maxlenij(int i,int j)/* gives maximum cycle
length for integers between and including i and j */
{int t=0,h,Clen,u;

if(j/2 > i)
{ Clen = len(j/2);/* It will give max Cycle Length
after the end of the loop */
for(u=j/2+1;u<=j;u++)
{
if( (u-1)/3 >=i && (u-1)%3 == 0 )
continue;
h = len(u);
if( h > Clen)
Clen = h;
}
}
else
{ Clen = len(i);/* It will give max Cycle Length
after the end of the loop */
for(u=i+1;u<=j;u++)
{ h = len(u);
if( h > Clen)
Clen = h;
}
}

return(Clen);
}



int len(int u)
{
if(u == 1)
{
return(1);
}
else if( u % 2 == 1)
{
u = 3*u + 1;
return(1 + len(u) );
}
else
{ u = u/2;
return(1 + len(u) );
}
}
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

What are you doing in "maxlenij"? All this dividing by 2 and 3 and stuff... is that really necessary?
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 »

That was not necessary but I observed that

if j/2 > i
then there is no need to check the cycle length of the int from i to j/2 as double of all these int will be in between j/2 + 1 to j which will have one more cycle length.

Similarly,all even int of the form 3n+1 where n is odd & between i & j need not be taken into account as n will have one more cycle length than 3n+1.

PLEAS E run my prog on your computer and tell me for which test data it gives wrong answer.
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

I quickly rewrote your program to use a simple loop that tries the whole interval and got it accepted.
10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

some comment

Post by 10153EN »

Tar79, actually I post here is not for help, but just to express my comment on your posts.

To me, and I think to some other programmers, to solve the problems is by myself. When there's something wrong or I think there's some tricky thing in the problem, what I will do is to ask for advice and hints. If I still get trapped after help, I will consider post the code here and I think some great and euthaustic helper, like Stefan Pochmann, will give me a hand.

Therefore I was surprised when you *order* the others to run your program and *tell* you what's wrong! I think, if there's someone give you a hand, you are really lucky! (Stefan Pochmann you are really great =P)

Also, as I mentioned in the other thread (I think you know which thread it is), please follow the rule of using this board~ As it's our place to share our experience in programming. I don't want the system administrator to feel the user "il-lawful".

If you think I am blaming you, sorry about that, but I just want to express what I want to say.
SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

This doesn't work?

Post by SilentStrike »

What is wrong with this code? It gives the correct response for the 4 test cases.

Code: Select all

#include <iostream>
#include <cstring>

long long getCycleLen(long long n) {
	long long len=1;
	while (1) {
		if (n == 1) {
			return len;
		}
		if (n & 1) {
			n = 3*n+1;
		} else {
			n/=2;
		}
		len++;
	}
}

int main() {
	long long min, max;
	while (std::cin >> min >> max) {
		long long maxCycleLen=1;
		for (long long i = min; i <= max; i++) {
			long long thisCycLen = getCycleLen(i);
			if (thisCycLen > maxCycleLen) {
				maxCycleLen = thisCycLen;
			}
		}
		std::cout << min << ' ' << max << ' ' << maxCycleLen << '\n';
	}
	return 0;
}
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

You might want to read one of the older threads about this problem, because your mistake has been discussed already over and over again...
SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

Post by SilentStrike »

I searched the forum for "100" in volume 1, but I didn't come up with anything. Could you point me to the thread where it was discussed?
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

In all of the following threads your exact mistake was explicitly discussed, and I didn't even list those where it was only covered in the programs.

What exactly do you mean when you say "I searched ..."?

It's a bit mean, I remember that it took me seven attempts to solve this problem when I first came here (back then when I was young and beautiful...)...

Try this one:
http://acm.uva.es/board/viewtopic.php?t=438

Or this one:
http://acm.uva.es/board/viewtopic.php?t=481

Or this one:
http://acm.uva.es/board/viewtopic.php?t=473

Or this one:
http://acm.uva.es/board/viewtopic.php?t=451

Or this one:
http://acm.uva.es/board/viewtopic.php?t=440

Or this one:
http://acm.uva.es/board/viewtopic.php?t=386

Or this one:
http://acm.uva.es/board/viewtopic.php?t=195

Or this one:
http://acm.uva.es/board/viewtopic.php?t=4

That's it, but by now I guess you already got my point.
10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

What's a pity that many threads are created for a single problem =P

And thank you, Stefan Pochmann, for listing all the *reference* threads! =D
SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

Post by SilentStrike »

Thanks. I searched and found the problem about the ordering and reversed the min and the max, but submitted them in the wrong order (always min first)... I got it eventually though. Thanks.
Yobbo
New poster
Posts: 1
Joined: Wed Jun 26, 2002 1:07 am

Prob 100

Post by Yobbo »

Hey guys, judge says 'Your program has not solved the problem. It ran during 0.030 seconds.'
To this program:
(problem 100)

@BEGIN_OF_SOURCE_CODE



/* @JUDGE_ID: 20603EH 100 C++ "Brute Force" */



/*

*

* Author: ME

* Date: June 25, 2002

* Purpose: http://acm.uva.es/p/v1/100.html

* 3n+1 problem

*

*/



#include <stdio.h>



void swap(int *x, int *y) { *x=*y+*x; *y=*x-*y; *x=*x-*y; }



void main ( void )

{

int i, j, firsti, firstj, counter=0, current, max=0;



while (scanf("%d %d",&i,&j)==2) {

firsti=i; firstj=j;

if ( i>j ) swap(&i,&j);

current=i;



while ( current!=j ) {

i=current;

while ( i!=1 ) {

if ( !(i % 2) )

i/=2;

else

i=3*i+1;

++counter;

}

if ( counter > max )

max=counter;

counter=1;

current++;

}

printf("%d %d %d\n",firsti,firstj,max);

max=0; counter=0;

}

}



@END_OF_SOURCE_CODE
-------------------------------
Graduated from HS 6/20/02
College starts 8/23/02
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

maybe "while( current <= j )" will work?
Post Reply

Return to “Volume 1 (100-199)”