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

Dragoon
New poster
Posts: 7
Joined: Sun Jun 09, 2002 5:51 am
Location: BC, Canada
Contact:

100, not solved?

Post by Dragoon »

Hi, I submitted 100 and judge says:
Dear Dragoon:

Your program has not solved the problem. It ran during 0.000 seconds.
Can someone help me out here, tell me what im doing wrong? Here is my code:
[cpp]
//judge@uva.es
//@JUDGE_ID: 20308JC 100 C++

#include <iostream.h>

int maxcycle(int n)
{
int count = 1;
while(n != 1)
{
if(n % 2)
n = 3 * n + 1;
else
n = n / 2;
count++;
}
return count;
}

int main()
{
int start = 0;
int end = 0;
int temp = 0;
int largest = 0;

cout << "Please enter 2 integers separated by a space or a new line:\n";

cin >> start;
cin >> end;

if(start > 0 && start < 10000 && end > 0 && end < 10000)
{
cout << start << " " << end << " ";

if(start < end)
{
while(start <= end)
{
temp = maxcycle(start);
if(temp > largest)
largest = temp;
start++;
}
}
if(start > end)
{
while(start >= end)
{
temp = maxcycle(end);
if(temp > largest)
largest = temp;
end++;
}
}

cout << largest << endl;
}
else
cout << "Integers must be between 0 and 10000.\n";
main();
return 0;
}
//@END_OF_SOURCE_CODE
[/cpp]
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

Printing "Please enter..." is not specified in the output, therefore it shouldn't be there.
littledump
New poster
Posts: 25
Joined: Wed Jun 05, 2002 4:55 am
Location: London, ON, Canada
Contact:

Post by littledump »

cout << "Integers must be between 0 and 10000.\n";

neither is that, but that else condition should never be satisfied anyway.

also might wanna throw a @begin_of_source in there to be safe :)
taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Output Limit Exceeded: 100

Post by taj79 »

Please run my program on your computer and tell me what is wrong and how could I correct it
I submitted my solution and the judge replied :

Your program output is greater (4231168 bytes) than the maximum
allowed for any problem by this judge (4194304 bytes).
You must interprete this as a Wrong Answer (in fact, is wrong!).
By some reason your program is writing an unlimited output.


My program:

#include<stdio.h>
#include<stdlib.h>
int maxlenij(int i,int j);
int len(int u);


main()
{ int t,i,j;
for(t=1;;++t)/* t = no. of pairs */
{
scanf("%d",&i);
if( i>0 && i<= 10000)
{ scanf("%d",&j);
printf(" %3d %3d %3d\n",i,j,maxlenij(i,j) );
}
else
break;
}
}

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) );
}
}
#include<stdio.h>
#include<stdlib.h>
int maxlenij(int i,int j);
int len(int u);


main()
{ int t,i,j;
for(t=1;;++t)/* t = no. of pairs */
{
scanf("%d",&i);
if( i>0 && i<= 10000)
{ scanf("%d",&j);
printf(" %3d %3d %3d\n",i,j,maxlenij(i,j) );
}
else
break;
}
}

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


Thanking you in anticipation,
taj
Dragoon
New poster
Posts: 7
Joined: Sun Jun 09, 2002 5:51 am
Location: BC, Canada
Contact:

Post by Dragoon »

Ok, I commented out the text... and judge still doesnt like it! Here is the updated code:
[cpp]//judge@uva.es
//@JUDGE_ID: 20308JC 100 C++
//@BEGIN_OF_SOURCE_CODE

#include <iostream.h>

int maxcycle(int n)
{
int count = 1;
while(n != 1)
{
if(n % 2)
n = 3 * n + 1;
else
n = n / 2;
count++;
}
return count;
}

int main()
{
int start = 0;
int end = 0;
int temp = 0;
int largest = 0;

// cout << "Please enter 2 integers separated by a space or a new line:\n";

cin >> start;
cin >> end;

if(start > 0 && start < 10000 && end > 0 && end < 10000)
{
cout << start << " " << end << " ";

if(start < end)
{
while(start <= end)
{
temp = maxcycle(start);
if(temp > largest)
largest = temp;
start++;
}
}
if(start > end)
{
while(start >= end)
{
temp = maxcycle(end);
if(temp > largest)
largest = temp;
end++;
}
}

cout << largest << endl;
}
// else
// cout << "Integers must be between 0 and 10000.\n";
// main();
return 0;
}
//@END_OF_SOURCE_CODE[/cpp]
10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

I seems that your program runs once only...

So do you assume that there's only one test case? =P
10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

in your code:

Code: Select all

for(t=1;;++t)/* t = no. of pairs */ 
{ 
scanf("%d",&i); 
if( i>0 && i<= 10000) 
{ scanf("%d",&j); 
printf(" %3d %3d %3d\n",i,j,maxlenij(i,j) ); 
} 
else 
break; 
} 
} 

The program will not jump to the else case. In other words, it loop infinitely.

Try to take a look at the return value of scanf.
Hope can help~

p.s. try don't post the code directly, and on the other hand, ask for hint and advice is a better approach to solve the problems, at least to me. Since it's not so good to ask the other to debug for you.
Dragoon
New poster
Posts: 7
Joined: Sun Jun 09, 2002 5:51 am
Location: BC, Canada
Contact:

Post by Dragoon »

well if i uncomment main(); at the end, it runs forever, resulting in an error from judge...
10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

Yes, expectedly. So you have to loop to the beginning when there's still input to be read.
Dragoon
New poster
Posts: 7
Joined: Sun Jun 09, 2002 5:51 am
Location: BC, Canada
Contact:

Post by Dragoon »

How is my program supposed to know if there's still input to be read? Its not like there is a time limit to wait for input...
Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal

Post by Betovsky »

run til theres no more input ( EOF )
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

Btw, your first posted program *did* make the main() call at the end. Please explain how the judge could tell you a time of 0.000 back then and now it would run forever. I don't understand.
Dragoon
New poster
Posts: 7
Joined: Sun Jun 09, 2002 5:51 am
Location: BC, Canada
Contact:

Post by Dragoon »

alright, i lied :D judge says this for the first code:
Dear Dragoon:

Your program output is greater (4236247 bytes) than the maximum
allowed for any problem by this judge (4194304 bytes).
You must interprete this as a Wrong Answer (in fact, is wrong!).
By some reason your program is writing an unlimited output.
Could someone please explain to me what EOF is?
Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal

Post by Betovsky »

EOF means end of file ... and that means when u reach the end of a file hehe

generally is the form i use to check the end of the input (there are some execptions)
cause generally i use and i think the judge uses too , redirecting files to the input of the
program...
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

Doesn't matter if it comes from a "file" or from "user input" or whatever. The mechanism is always the same.

I usually write sth like this:

int i, j;
while( cin >> i >> j ){
...
}

That is, as long as cin can give me more, I work more.
Post Reply

Return to “Volume 1 (100-199)”