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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: problem no 100 Time Limit Exceeded

Your code is stuck in an infinite loop. Try doing something like this instead:
while(scanf("%d %d",&num1,&num2) == 2) {
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: problem no 100 Time Limit Exceeded

I used that loop coz in the problem description it is not clear that how many test cases there are. When i used this : while(scanf("%d %d",&num1,&num2)==2) it runs and works well in my compiler but after submitting here it says compilation error.... brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: problem no 100 Time Limit Exceeded

Post your full updated code if you still need help. You have to read until the end of stdin and then terminate. You can click see the reason for your compile error by clicking My Submissions: http://uva.onlinejudge.org/index.php?op ... e&Itemid=9
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: problem no 100 Time Limit Exceeded

My updated code is here:
#include<stdio.h>

int len(int x)
{
int max;
max=1;
while(x>1)
{
max++;
if(x%2==0) x=x/2;
else x=3*x+1;

}
return max;
}

int main()
{
int i,prev,a,b,max,num1,num2;

while(scanf("%d %d",&num1,&num2)==2)
{

max=0;

a=len(num1);
if(num1==num2) {max=a; goto here;}

for(i=num1;i<=num2;i++)
{

b=len(i);
if(a>b)
{
max=a;
}
else
{
max=b;

a=b;
}
}
here:
printf("%d %d %d\n",num1,num2,max);
}
return 0;
}

now it says wrong answer...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: problem no 100 Time Limit Exceeded

i may be greater than j.
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: problem no 100 Time Limit Exceeded

this same code i just converted in C++ and then got AC what's the problem in ANSI C???? brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: problem no 100 Time Limit Exceeded

Input:

Code: Select all

1 10
10 1
AC output:

Code: Select all

1 10 20
10 1 20
Your code that you posted is failing this I/O. I'd have to see what you changed when converting to explain why your new C++ code is AC. It is possible to solve this problem in ANSI C.
Check input and AC output for thousands of problems on uDebug!

ron2794
New poster
Posts: 4
Joined: Thu May 23, 2013 7:13 pm

UVA 100 : 3n +1 : Runtime error.

Here is my code, can you help me in figuring out why this is a Runtime error !

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;

int *ar,*arr;

int find(unsigned int a,unsigned int u,unsigned int uu){
int n=1;
while(a!=1){
if(a<=uu && a>=u && ar[a-u]!=-1) return (n-1)+ar[a-u];
if(a%2) a=3*a+1;
else a/=2;
n++;
}
return n;
}

int main(int argc, char *argv[]){
int a=1,b=1000000;
//cout << find(b,a,b)
int i;

while(scanf("%d %d",&a,&b)!=EOF){
ar = (int*)malloc(sizeof(int)*(b-a+1));
ar=(int*)memset(ar,-1,sizeof(int)*(b-a+1));
int max=0;
for(i=a;i<=b;i++){
ar[i-a]=find(i,a,b);
if(ar[i-a]>max) max=ar[i-a];
}
cout << a << " "<< b << " "  << max << endl;
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: UVA 100 : 3n +1 : Runtime error.

What if i > j?
Check input and AC output for thousands of problems on uDebug!

ron2794
New poster
Posts: 4
Joined: Thu May 23, 2013 7:13 pm

Re: UVA 100 : 3n +1 : Runtime error.

i haven't taken care of that, but that is really a stupid input which i am not expecting at all ....

but if that is the case, what we need to do ?

ron2794
New poster
Posts: 4
Joined: Thu May 23, 2013 7:13 pm

Re: UVA 100 : 3n +1 : Runtime error.

phew, thanx, accepted at last !
AC !

RoniphpBB
New poster
Posts: 10
Joined: Sat Feb 09, 2013 11:22 am

Re: If you get WA in problem 100, read me before post!

Thanks brianfry713 finally i got AC
Last edited by RoniphpBB on Sat Jun 15, 2013 11:44 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: If you get WA in problem 100, read me before post!

What if i > j ?
Check input and AC output for thousands of problems on uDebug!

Ardeshir81
New poster
Posts: 8
Joined: Wed Jun 12, 2013 5:51 pm

Re: If you get WA in problem 100, read me before post!

HI Everyone.
I'm getting WrongAnswer too.
I don't understand why, this is my code :

Code: Select all

//All input integers will be less than 1,000,000 and greater than 0 .
//There will be 2 inputs , i and j , for all integers from i to j we should get the Cycle-Length of '3n + 1' formula and return the maximum .

#include <iostream>

using std :: cout ;
using std :: cin ;
using std :: endl ;

int main ()
{
int i , j , CL = 1 , maxCL , tmp ; //CL is the Cycle-Length of the current number and maxCL is the maximum Cycle-Length and tmp is the temporary number which the operation will be done on .
cin >> i >> j ;
cout << i << " " << j << " " ; //We do not use an extra variable for numbers between i and j , we use the i itself in the for loop , so we'll lose the i at the end of the program .
if (i > j)
{
int swapij ;
swapij = i ;
i = j ;
j = swapij ;
}
maxCL = 0 ;
for ( ; i <= j ; i ++)
{
tmp = i ;
while (tmp > 1)
if (tmp %2 == 0)
{
tmp /= 2 ;
CL ++ ;
}
else
{
tmp = tmp * 3 + 1 ;
CL ++ ;
}
if (CL > maxCL)
maxCL = CL ;
CL = 1 ;
}
cout << maxCL << endl ;
return 0 ;
}
I compared my answers with the upper post, in this case :
99999 1 525
but I get 999999 1 476

Where of my code is wrong? THNX

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: If you get WA in problem 100, read me before post!

You need to keep reading sets of i and j until the end of the input, you're only reading one.
Check input and AC output for thousands of problems on uDebug!