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

Post by brianfry713 » Tue Apr 09, 2013 3:08 am

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

Post by triplemzim » Tue Apr 09, 2013 11:22 pm

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 by brianfry713 » Wed Apr 10, 2013 11:59 pm

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

Post by triplemzim » Sat Apr 20, 2013 2:28 am

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

Post by brianfry713 » Mon Apr 22, 2013 11:38 pm

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

Post by triplemzim » Fri Apr 26, 2013 1:42 am

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

Post by brianfry713 » Sat Apr 27, 2013 2:07 am

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.

Post by ron2794 » Thu May 23, 2013 7:19 pm

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.

Post by brianfry713 » Thu May 23, 2013 11:02 pm

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.

Post by ron2794 » Fri May 24, 2013 7:09 pm

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.

Post by ron2794 » Fri May 24, 2013 7:19 pm

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!

Post by RoniphpBB » Wed May 29, 2013 1:31 am

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!

Post by brianfry713 » Wed May 29, 2013 11:49 pm

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!

Post by Ardeshir81 » Wed Jun 12, 2013 6:11 pm

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!

Post by brianfry713 » Thu Jun 13, 2013 12:46 am

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!

Post Reply

Return to “Volume 1 (100-199)”