100 - The 3n + 1 problem

[Rale]

I got a WA again.

It ran for a little bit more than 5 seconds, and the answer is WRONG!

My code is two posts up, what's wrong with it????

I only changed that to cycle(0).

[Rocky]

i aslo change some thing i add a new line charecter after the output.....

Code: Select all

printf ("%d %d %d\n",n1,n2,max); //"\n" after each output...

do you change it....

Good Luck
Rocky

[spicy_hair]

diego andres de barros

NEVER use long long int. they are evil. i changed all your "long long int" to "int" and the programworked out perfectly

ps: emotional blind is right, "after getting ACCEPTED dont forget to REMOVE your code from here"

gl

[emotional blind]

diego andres de barros

NEVER use long long int. they are evil. i changed all your "long long int" to "int" and the programworked out perfectly

gl

i disagree with u.
the only problem is tle there,
and my previous post will fix it
but ur method doesnot overcome tle
thanks

[spicy_hair]

spicy_hair wrote:
diego andres de barros

NEVER use long long int. they are evil. i changed all your "long long int" to "int" and the programworked out perfectly

gl


i disagree with u.
the only problem is tle there,
and my previous post will fix it
but ur method doesnot overcome tle
thanks

well i tried ur method and got ac. however when i try it on my computer with sample input i got the following output:

sample input:
1 10
100 200
201 210
900 1000

output on my computer:
1 0 10
100 0 200
201 0 210
900 0 1000

clearly its not the correct output. can you explain wat happened?

thanx

[mf]

Perhaps, the libraries with which programs are linked on your computer don't support %lld format. You may try to use %I64d instead.
On UVa's judge %lld works fine.

[spicy_hair]

i c

thanx

[diego andres de barros]

thaks for help me!!!!!!!!!!!

[jtmh]

The input description says:

You can assume that no opperation overflows a 32-bit integer.

But, actually, there is a total of 883 occurrences where a "3n + 1" operation overflows a 32-bit unsigned integer; in particular, a maximum value of 56,991,483,520 will be reached if the original n is 704,511. Could someone correct this? Thank you.

[little joey]

There is nothing wrong with the description (apart from the misspelling of the word 'operation'). It simply states that there will be no input values for which the intermediate results are too big to fit into a 32-bit number.

[daishengqi]

This is my code:

#include <stdio.h>

void main()
{
long i,j,k,n=0,temp,tempn=0;
while (scanf("%ld %ld",&i,&j)!=EOF)
{
if (i>j)
{
temp=i;
i=j;
j=temp;
}

for (k=i;k<=j;k++)
{
temp=k;
while (temp != 1 )
{
if (temp % 2!=0)
{
temp=temp+temp+temp+1;
}
else
{

temp=temp>>1;
}
tempn++;
}
if (tempn> n)
n=tempn;
tempn=0;
}
printf("%ld %ld %ld\n",i,j,n+1);
}
}
============================
I don't know why WA......It seems that there's nothing wrong with it..

[jtmh]

I see. I misunderstood its meaning. Thanks a lot.

[abhi]

i dont know if u've got AC already but anyway u need to re-initialise n to zero each time u accept new pair of i/p

[Chiech]

#include<iostream.h>

void main()
{
unsigned long i,j,cup;
long m;
do
{
cin>>i>>j;
}while(i<=0||i>1000000||j<=0||j>1000000);

m=j-i+1;

if(m<0)
{
m=i-j+1;
cup=i,i=j,j=cup;
}
else
{
cup=i;
}

unsigned long *a1_array=new unsigned long [j*3];
unsigned long *a2_array=new unsigned long [j*3];
unsigned long n,x,y=1;
start:
x=1,n=1;cup=i;
for(x=1;;x++)
{
*(a1_array+x)=cup;

if(cup==1)
{
*(a2_array+y)=n;
y++;
i++;
if(i>j)
{
goto end;
}
goto start;
}
else if(*(a1_array+x)%2==0)
{
n++;
cup=*(a1_array+x)/2;
continue;
}
else
{
cup=3*cup+1;
n++;
continue;
}
}
end:
i=j-m+1;

unsigned long z;
*(a2_array)=0;

for(z=1;z<y;z++)
{
if(*(a2_array)<*(a2_array+z)){*(a2_array)=*(a2_array+z);}
}
cout<<i<<"\t"<<j<<"\t"<<*(a2_array)<<"\n";
delete[] a1_array;
delete[] a2_array;

}
============================================
please help me~

[toyman]

this is the #100 problem "The 3n+1"

Code: Select all

#include<iostream>
using namespace std;
int compute(unsigned int ,unsigned int ,unsigned int );   //define function                 
main()
{
    unsigned int h,i,j,max;                    //define variables
    unsigned int temp[5000];                       
    cout<<"enter two number i,j:";         //enter two number as it's range
    cin>>i>>j;
    for(h=j;h>=1;h--){    
       temp[h]=compute(h,i,j);       //store the count's times into temp[i]
    }
    max=temp[1];                     //set max as temp[1]
    for(h=1;h<=j;h++){               //for Loop 
       if(temp[h]>max){              //if temp[i]>max 
           max=temp[h];              //max =temp[i] 
       }           
    }
    cout<<"maximum cycle length:"<<max<<endl;  //output maximum cycle length 
    //system("pause");
    return 0;
}
int compute(unsigned int x,unsigned int a,unsigned int b)
{
    int count=1;      //define variables
    if(x>=a&&x<=b){        //x must be the range of a and b(same as i and j) 
        while(x!=1){       //do while loop untill x==1 then stop
            if(x%2)        //if x is odd
                x=3*x+1;   //x=3*x+1
            else           //if x is even
                x=x/2;     //x=x/2
            count++;       //count = count + 1
        }
        return count;      //return count's value to main function
    }
    return 0;
}

that is my code!!
i try in my computer is correct,but i upload it to Internet is Wrong Answer! Plz indicate my bug is where!!3Q....

Then i want to ask the input
Sample Input
1 10
100 200
201 210
900 1000

is enter 4 pair of value in same time??
and output the four pair of value in same time??

Code: Select all

Code: Select all