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

Austin
New poster
Posts: 4
Joined: Sat Jun 26, 2004 9:29 am
Location: Bangladesh

What's wrong in it? prob 100

Post by Austin »

Everytime i'm receiving this Wrong Answer reply including
"Your program has not solved the problem. It ran during 0.002 seconds."

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


int function(int k);
int count;
void main()
{
int m,n,i,temp,maxCount,tempCount;

scanf("%d %d",&n,&m);


if(n>m)
{
temp=n;
n=m;
m=temp;

}

maxCount=function(n);
for(i=n+1;i<=m;i++)
{
tempCount=function(i);
if(maxCount<tempCount)
{ temp=tempCount;
tempCount=maxCount;
maxCount=temp;
}


}

printf("\n %d %d %d",n,m,maxCount);

}


int function(int k)

{ count=1;

while(k!=1)
{ count++;
if((k%2)==0)
k=k/2;
else
k=3*k+1;
}

return count;

}

But compiler in my pc giving the required result.
so, What's the problem in it?????? :-?

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

Your program solves the problem for one set of input. But the judges data file contains many lines of input.

There is a popular sticky thread regarding this problem. Please view it if you continue to have trouble regarding this problem.

Austin
New poster
Posts: 4
Joined: Sat Jun 26, 2004 9:29 am
Location: Bangladesh

Post by Austin »

Thanks for the reply. I've simply changed the following thing

while(scanf("%d %d",&n,&m)!=EOF)

And the entire code is as follows:

/* @JUDGE_ID: 47052RM 100 C "3n+1 problem" */



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


int function(int k);
int count;
main()
{
int m,n,i,temp,maxCount,tempCount;

while(scanf("%d %d",&n,&m)!=EOF) {

if(n>m)
{
temp=n;
n=m;
m=temp;

}

maxCount=function(n);
for(i=n+1;i<=m;i++)
{
tempCount=function(i);
if(maxCount<tempCount)
{ temp=tempCount;
tempCount=maxCount;
maxCount=temp;
}


}

}

printf("\n %d %d %d",n,m,maxCount);


}

int function(int k)
{ count=1;

while(k!=1)
{ count++;
if((k%2)==0)
k=k/2;
else
k=3*k+1;
}

return count;

}

But this time it gives compile error.

Here are the compiler error messages:

02623883_24.c:38: parse error before string constant
02623883_24.c:38: warning: data definition has no type or storage class

Can u pls help me??
I'm a new learner of C.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

I don't think it gives compile error. I submitted the code and it got WA.

I think you better use the Submit-o-matic to submit the problems, instead of submitting through mail.

Here is the link: http://acm.uva.es/p/submit.php

As for the WA, I ran yourd code using VC6, your program only produces output for the very last case. :wink:

Austin
New poster
Posts: 4
Joined: Sat Jun 26, 2004 9:29 am
Location: Bangladesh

Post by Austin »

I've modified my code:


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


long function(long k);
int count;
void main()
{
long m,n,temp,maxCount,tempCount;
long i;

while(scanf("%ld %ld",&n,&m)!=0)

{ if(n>m)
{
temp=n;
n=m;
m=temp;

}

maxCount=function(n);
for(i=n+1;i<=m;i++)
{
tempCount=function(i);
if(maxCount<tempCount)
maxCount=tempCount;


}

printf("\n %ld %ld %ld",n,m,maxCount);

}


}

long function(long k)
{ count=1;

while(k!=1)
{ count++;
if((k%2)==0)
k=k/2;
else
k=3*k+1;
}

return count;

}

This time it shows time exceeded. Your program took 10.09 sec.

If i use
while(scanf("%d %d",&n,&m)!=0)
it takes 10.09 secs

If i use
while(scanf("%d %d",&n,&m!=EOF)
it takes 4.09 secs, But even in this case the program is not being accepted.

I'm getting crazy.

:o

Md. Azam Khan
New poster
Posts: 8
Joined: Tue Jun 15, 2004 7:16 pm
Location: Chittagong, Bangladesh
Contact:

Post by Md. Azam Khan »

Hellow new comer!
Welcome to programmers zone. u didn't write the problem no! Though i thought the code is for problem no 100. Anyway, u should know how to write code first. Notice carefully where i modified your code. Another thing, think about variable length.

#include<stdio.h>
#include<stdlib.h> //why do you include this header file?


int function(int k); //long k
int count;
void main()
{
int m,n,i,temp,maxCount,tempCount; //not int u can use long and add two variable ori1,ori2 for keeping original value of n and m.

scanf("%d %d",&n,&m); //u should read eof or just write: while(scanf("%ld %ld",&n,&m)==2)
{//begin of the while loop
ori1=n;
ori2=m;

if(n>m)
{
temp=n;
n=m;
m=temp;

}

maxCount=function(n);
for(i=n+1;i<=m;i++)
{
tempCount=function(i);
if(maxCount<tempCount)
{ temp=tempCount;//unnecessary line
tempCount=maxCount; //unnecessary line
maxCount=temp; //tempCount instead of temp
}


}

printf("\n %d %d %d",n,m,maxCount); //printf("%ld %ld %ld\n",ori1,ori2,maxCount); }//end of while loop.

}


int function(int k) //long k

{ count=1;

while(k!=1)
{ count++;
if((k%2)==0)
k=k/2;
else
k=3*k+1;
}

return count;

}

There still may have some error or not. Just try to understand the code that i changed or tried to change. If u fail in this time then plz just mail me: a_khanss@yahoo.com to help more. Wishing best of luck.

I born to code :evil:

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

Well here is the mistake:

if input is

10 20

output should be

10 20 21

if input is

20 10

output should be

20 10 21

Hope this helps :wink:

beautidays
New poster
Posts: 1
Joined: Fri Jul 16, 2004 7:43 am

what's the problem??

Post by beautidays »

#include <iostream>
using namespace std;



int main()
{
int t, first, count,last, max=0;

while(cin >> first >> last){
cout << first << " " << last << " ";
if(first>=last)
{
t = first;
first = last;
last = t;
}

int i, j;

for(i=first;i<=last;i++)
{
if(i!=1)
{
j=i;
count = 1;
while(j!=1)
{
if(j%2==0)
j = j/2;
else
j = j*3+1;
count++;
}
}
else
count = 2;
if(count > max)
max = count;
}
cout << max << endl;
}

return 0;
}
Last edited by beautidays on Fri Jul 16, 2004 8:49 am, edited 1 time in total.

gibber
New poster
Posts: 2
Joined: Mon Jul 12, 2004 6:36 am

Post by gibber »

I just changed your program a little,but I got AC,can you find the difference between yours and mine? :wink:

Code: Select all

[cpp]
#include <iostream> 
using namespace std; 



int main() 
{ 
int t, first, count,last,max; 

while(cin >> first >> last){ 
max=0;
cout << first << " " << last << " "; 
if(first>=last) 
{ 
t = first; 
first = last; 
last = t; 
} 

int i, j; 

for(i=first;i<=last;i++) 
{ 
if(i!=1) 
{ 
j=i; 
count = 1; 
while(j!=1) 
{ 
if(j%2==0) 
j = j/2; 
else 
j = j*3+1; 
count++; 
} 
} 
else 
count = 2; 
if(count > max) 
max = count; 
} 
cout << max << endl; 
} 

return 0; 
}
[/cpp]
I enjoy programming!!!

kaydara
New poster
Posts: 1
Joined: Mon Jul 19, 2004 3:06 pm

Post by kaydara »

i have read and dont find answer for me, i always get Wrong Answer and tryed both ways, code and file:

[c]#include<stdio.h>

int ciclo(int x)
{
int cont=0;
while(1)
{
cont++;
if(x==1) return cont;
else
{
if(x%2==0) x=x/2;
else x=3*x+1;
}
}
return cont;
}


int main()
{
int a,b,i,temp=0,max=0;
while(scanf("%d %d",&a,&b)==2)
{
if(a<1 || a>1000000) return 0;
if(b<1 || b>1000000) return 0;
for(i=a;i<=b;i++)
{
temp=ciclo(i);
if(temp>max) max=temp;
}
printf("%d %d %d\n",a,b,max);
temp=0;
max=0;
}
return 0;
}
[/c]

Whats the problem? any1 know?

nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

Post by nightdog »

by looking quikly at your code i believe your problem is that you forgot to add an if-clause to handle switched input (cases that a > b).

cheers,
Ricardo Cabral

wk
New poster
Posts: 7
Joined: Tue Jul 20, 2004 4:49 am

Post by wk »

fpnc wrote:I don't know either. You can see my submission got AC (and it was a copy-and-paste submission of your first code).

Anyway, please note down the full submission number when you find this kind of things as we can retrieve your submissions and try to find out what happens.
I'm having saort of same problems, so
following your advice, what should I do
with the submission numbers?

wk
New poster
Posts: 7
Joined: Tue Jul 20, 2004 4:49 am

Post by wk »

Here are my two submission numbers:
2697786
2697732

wk
New poster
Posts: 7
Joined: Tue Jul 20, 2004 4:49 am

Post by wk »

Considernig my problems with the problem 100,
I believe I know what is wrong.

THE PROBLEM IS STATED INCORRECTLY.
<problem>
You can assume that no opperation overflows a 32-bit integer.
</problem>

This is NOT TRUE!!!
Computing the cycle length for 113383
overflows 32-bit integer on step 120,
where n=827370449

How come NOBODY HAS NOTICED IN SO MANY YEARS?

I can only assume you people meant unsigned
integer. If so you should have said so.
Because if you say 32-bit integer, most
people understands 32-BIT INTEGER.
32-bit INTEGER IS A __SIGNED__ INTEGER, in all
languages I know (and know of).

PS:
Sorry for all these CAPS, but this nonsense
has caused me to waste way too much time.

wk
New poster
Posts: 7
Joined: Tue Jul 20, 2004 4:49 am

Post by wk »

Funny, now my code gets accepted - unchanged
since I last tried to post it and got WA.

Now, on the subject of int overflow: looked
at most of the C/C++ code from this thread
and all the code i looked at IS __WRONG__
and apparently got accepted anyway (if
someone is interested then the test
with n = 113383 could prove interesting).
Go figure.

Also, could someone explain why in 100
and 110 I got PE? I figure if the program
in 110 shall fail compilation it should
be rejected, and if the writelines were
not on separate lines it should be rejected
as well. What else is there???
Now on 110: I'm using
printf("%s %s %d\n", blah, blah, blah)
What could possibly be wrong here?

I'd love to solve some more problems
but I'd hate for any more of my time being
wasted.
Could someone explain what is happening here?

Post Reply

Return to “Volume 1 (100-199)”