100  The 3n + 1 problem
Moderator: Board moderators
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.
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.
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( (u1)/3 >=i && (u1)%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) );
}
}
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( (u1)/3 >=i && (u1)%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) );
}
}

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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.
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.

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
some comment
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 "illawful".
If you think I am blaming you, sorry about that, but I just want to express what I want to say.
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 "illawful".
If you think I am blaming you, sorry about that, but I just want to express what I want to say.

 New poster
 Posts: 22
 Joined: Fri Jan 04, 2002 2:00 am
This doesn't work?
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;
}

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:

 New poster
 Posts: 22
 Joined: Fri Jan 04, 2002 2:00 am

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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.
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.

 New poster
 Posts: 22
 Joined: Fri Jan 04, 2002 2:00 am
Prob 100
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
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
Graduated from HS 6/20/02
College starts 8/23/02

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact: