100 - The 3n + 1 problem

[mf]

Code: Select all

if (!cin) break;

[chunyi81]

Code: Select all

while (cin >> a >> b)
{
    // process input
}

will work as well.

[rafastv]

I'm getting Time Limit Exceeded always can somebody tell me what am I doing wrong?

Code: Select all

#include <stdio.h>
#include <math.h>

float max_ciclos(float);

int main(int argc,char **argv){
	unsigned long int i,j,k,a,b;
	float c,aux;
	float vetor[1000000];
	
	for (k=1;k<1000000;k++)
		vetor[k]=max_ciclos((float)k);
	while((scanf("%lu %lu",&i,&j))!=EOF){
	c=0.0;
	if (i>j){
		a=j;
		b=i;
	} else {
		a=i;
		b=j;

	}
	for (k=a;k<=b;k++){
		aux=vetor[k];
		if (aux>c)
			c=aux;
	}
	printf("%lu %lu %0.0f\n",i,j,c);
	}
	return 0;
}


float max_ciclos(float n){

float ciclos,t;

ciclos=0.0;
t=0.0;

while (n>1.0){	
	ciclos=ciclos+1.0;
	if (n==1.0) break;
	else{
		t=(n/2.0)-floor(n/2.0);
		if (t>0.0)
			n=(3.0*n)+1.0;
		else
			n=n/2.0;
	}	
}
ciclos=ciclos+1.0;
return ciclos;
}

[rafastv]

Changed the code, read the thread but still got WA, no longer TLE though

Code: Select all

#include <stdio.h>
#include <math.h>

float vetor[1000000];
float max_ciclos(float);

int main(int argc,char **argv){
	unsigned long int i,j,k,a,b;
	float c,aux;

	
	for (k=0;k<1000000;k++)
		vetor[k]=0.0;
	while((scanf("%lu %lu",&i,&j))!=EOF){
	c=0.0;
	if (i>j){
		a=j;
		b=i;
	} else {
		a=i;
		b=j;

	}
	if ((a>0) && (a<1000000))
	if ((b>0) && (b<1000000))
	for (k=a;k<=b;k++){
		aux=max_ciclos((float)k);
		if (aux>c)
			c=aux;
	}
	printf("%lu %lu %0.0f\n",i,j,c);
	}
	return 0;
}


float max_ciclos(float n){

float ciclos,t;
long int v; 
ciclos=0.0;
t=0.0;
v = (long int) n;
if (vetor[v]!=0.0)
	return vetor[v];
while (n>1.0){	
	ciclos=ciclos+1.0;
	t=(n/2.0)-floor(n/2.0);
	
	if (t>0.0)
		n=(3.0*n)+1.0;
	else
		n=n/2.0;
}
ciclos=ciclos+1.0;
vetor[v]=ciclos;
return ciclos;
}

[mf]

Don't use floats: they're slow and very imprecise - with 23 bits mantassa they can only exactly represent integers up to about 8*10^6.

Use int's. In case you didn't know, in C/C++ expressions a/b and a%b (for integer a and b) mean quotient (floor(a/b)) and remainder of division.

[rafastv]

Thanks changed the code to long int and solved it
Just for curiosity, well the choice I made for float types is because they do carry a more representative type than integers at least when I looked at floats.h

FLT_MAX=340282346638528859811704183484516925440.000000

while max integers are short unless you are using long int with a word of 64 bits(limits.h)

LONG_MAX=INT_MAX=2147483647

LONG_MAX(with 64 word)=9223372036854775807(long long)

So float is able to carry much more...but I'm having trouble though in others problems with operations on big numbers like float(this is not the first time). how can I store a number like 11111111111111111111111111111111111111111111111111111111111.0 on a long double for instance? any tips?

[imkat]

I tried many inputs and the outputs were all correct.However,I still get a WA.here is my code:

Code: Select all

const maxn=1000000;
var
   i,a,b,max:longint;
   l:array[0..maxn] of longint;
function tryl(n:int64;t:longword):longint;
var
    nextn:int64;len:longint;tmp:extended;
begin
    if n<=maxn then begin
        if l[n]>0 then tryl:=l[n]+t else begin
            if n mod 2=0 then tmp:=n div 2 else tmp:=n*3+1;
            nextn:=round(tmp);
            len:=tryl(nextn,t+1);
            tryl:=len;
            if n<=maxn then l[n]:=len-t;
        end;
    end else begin
        if n mod 2=0 then tmp:=n div 2 else tmp:=n*3+1;
        nextn:=round(tmp);
        len:=tryl(nextn,t+1);
        tryl:=len;
        if n<=maxn then l[n]:=len-t;
    end;
end;
begin
    l[1]:=1;
    for i:=2 to maxn do begin
        l[i]:=tryl(i,0);
    end;
    while true do begin
        if eof() then break;
        readln(a,b);
        max:=0;
        if a<=b then begin
            for i:=a to b do begin
                if l[i]>max then max:=l[i];
            end;
        end else begin
            for i:=b to a do begin
                if l[i]>max then max:=l[i];
            end;
        end;
        writeln(a,' ',b,' ',max);
    end;
end.

Why is it WA?

[crash.virus]

//Online Judge 100 Problem
#include<iostream>

using namespace std;
int solution(int,int);

int main()
{
int input[100][3]={0};
int temp1,temp2;
int counter=0;
while(cin >> temp1 >> temp2)
{
input[counter][0]=temp1;
input[counter][1]=temp2;
counter++;
}
for(int i=0;input[0]!=0;i++)
{
input[2]=solution(input[0],input[1]);
}
for(int i=0;input[0]!=0;i++)
{
cout << input[0] << " " << input[1] << " " << input[2] << endl;
}
cout << endl;
system("pause");
}

int solution(int a,int b)
{
int highest=0;
int temp;
int counter;
for(int i=a;i<=b;i++)
{
temp=i;
counter=0;
while(temp!=1)
{
if(temp%2==0)
temp/=2;
else
temp=3*temp+1;
counter++;
}
highest=(counter>highest?counter:highest);
}
return highest+1;
}

Can Any One Please Tell Me what is the problem with this code
I am new to online judge and programming

[raza]

Hi,
I am new to online-judge.uva.es . Just to get started , i solved the 3n+1 problem which works perfectly on my machine where i use Dev-C++ 4.9.9.2 IDE and the OS is Windows XP and the language im using to code is C.
Dev-C++ is using gcc as the compiler and my program compiles without any errors or warnings on my machine but when i submit it via submit-o-matic i get a compile error.

Heres my code :

Code: Select all

#include <stdio.h>

main()
{
    
     int i , j , num , temp , iOriginal , jOriginal , max_length = 0 ;

     while(scanf("%d %d",&i,&j) == 2)
     {

          iOriginal = i ;

          jOriginal = j ;
           
         //Swap i and j if out of order

         if(i > j)
         {
              temp = i ;

              i = j ;

              j = temp ;

         }


         for(num = i ; num <= j ; num++)
         {
                 temp = calculate_cycle_length(num);

                 if(temp > max_length)
                         max_length = temp ;

         }

         printf("%d %d %d\n",iOriginal,jOriginal,max_length);

         max_length = 0 ;

            

     }
     

}

int calculate_cycle_length(int num)
{

    int cycle_length = 0 ;

    do
    {

        if(num%2 == 0)
             num/=2 ;
        else
             num = (num*3)+1 ;

        cycle_length++ ;    
 
    }while(num != 1);   

    cycle_length++ ;  //Count the 1 at the end too

    return cycle_length ;    

    
}

Please help.

Thanks

[little joey]

Welcome to UVA.

We like to keep the forums as clean as possible, to make it easier to find information in them. With the great amount of problems and users trying to solve them, we issued a simple rule: if a thread exists for a particular problem, please use it and don't create a new one. For problem 100 there already exists an enormous amount of threads, so it would have been better if you used one of them.

When you submit your code to the UVA judge, the judge will send you a response email with the result. In case of a compiler error, it will send you the compiler output, so you can use that to debug your code. You may have to enable the appropriate option on your user profile.

In this particular case, the function call to calculate_cycle_length() appears in main() before it's declared or defined. So either put a declaration at the top of your code or change the order of the two fumctions.

[mf]

So float is able to carry much more...

It can represent exactly only about 5 most-significant digits. The rest are lost in rounding.

how can I store a number like 11111111111111111111111111111111111111111111111111111111111.0 on a long double for instance? any tips?

There's no standard data type to hold it, that doesn't round most of these digits right away.

[raza]

I am getting a WA. I dont know why i am getting it because the code is working perfectly fine on my machine.I using C language to code and Dev-C++ 4.9.9.2 as the IDE .

Heres my code :

Code: Select all

#include <stdio.h>

main()
{
    
     long int arr[1000][2] , num1 , num2  ;

     long int  i , j , cycle_length , max_cycle_length =0 ;

     int ctr = 0 ;

     long int calculate_cycle_length(long int);

     while(scanf("%ld %ld",&i,&j) != EOF)
     {
           arr[ctr][0] = i ;

           arr[ctr][1] = j ;

           ctr++ ;          
     }

          
     for(i = 0 ; i < ctr ; i++)
     {

           if(arr[i][0] > arr[i][1])
           {
                        num1 = arr[i][1] ;

                        num2 = arr[i][0] ;

           }
           else
           {
                        num1 = arr[i][0] ;

                        num2 = arr[i][1] ;    
           }

           for(j = num1 ; j <= num2 ; j++)
           {
                cycle_length = calculate_cycle_length(j);

                if(cycle_length > max_cycle_length)
                                max_cycle_length = cycle_length ;
           }

           printf("\n%ld %ld %ld",arr[i][0],arr[i][1],max_cycle_length);

           max_cycle_length = 0 ;

     }
                
          
     

}

long int calculate_cycle_length(long int num)
{

    long int cycle_length = 0 ;

    do
    {

        if(num%2 == 0)
             num/=2 ;
        else
             num = (num*3)+1 ;

        cycle_length++ ;    
 
    }while(num != 1);   

    cycle_length++ ;  

    return cycle_length ;    

    
}

Please help..Thanks

[raza]

Thanks for the reply little_joey . The compiler error goes when I remove the // comments from my code and also as you correctly said by changing the order of the functions. I can understand that some compilers like the one at uva can be very strict about function declarations and the order in which they are defined but why doesnt the compiler support these comments ??.
Anyways,now im getting a WA and following your advice ive posted my query here.
http://online-judge.uva.es/board/viewto ... highlight=

Please help me out.

Thanks a lot

[little joey]

About comments: the double slash ("//") is not valid in traditional C, so either use the "/*" - "*/" pair, or submit your code as C++.

I notice that you store all input in an array, before calculating and printing the results. This is possible, but better is to get the cases one at the time and immediately calculate and print the results. The number of input cases in undetermined, and 1000 may be to small.

Your answer for the case "1 1" is incorrect. Think about it.

Why do you print the newline at the beginning of your output? You'll get presentation error, even if the answer would be correct. The newline belongs at the end of your output line.

Read the documentation on the scanf() function. "while(scanf("%ld%ld",&i,&)!=EOF)" might work in some cases, but you should use "while(scanf(..)==2)": scanf returns the number of successfully read items, which is two in this case.

Hope it helps.

[Jan]

Search the board first. Dont open a new thread if there is one already.