100 - The 3n + 1 problem

[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]

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]

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]

What are you doing in "maxlenij"? All this dividing by 2 and 3 and stuff... is that really necessary?

[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]

I quickly rewrote your program to use a simple loop that tries the whole interval and got it accepted.

[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]

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]

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]

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]

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]

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]

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]

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

[Stefan Pochmann]

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