100 - The 3n + 1 problem

[mac]

Isn't that for the c++ language though? How could I do that in c?

[LithiumDex]

Not sure, maybe scanf returns a value?

[mac]

Yes, it returns the number of integers scanned. It didn't work at first, but I fixed it and got accepted. Woo! thanks again for the help.

[akim]

DOH! Thanks

I've been scratching my head trying to figure out why my program constantly exceeded the time limit. couldn't realy optimize it much more (with my limited knowledge ). But ofcourse I was assuming j would allways be the high number, causing an infinate loop... Silly me

Finaly got accepted. Thanks once again.

[898989]

Salamo Aleko
Just change the way you read with..Ur code might not reading the last test case...Or ...I realy do not know.
But to get ac

Code: Select all

int main() { 
	int i,j; 
	
	while(cin>>i>>j) { 
		if (i<j) 
			cout<<i<<" "<<j<<" "<<max_cyclic(i,j)<<endl; 
		else 
			cout<<i<<" "<<j<<" "<<max_cyclic(j,i)<<endl; 
	} 
	return 0; 
} 

Instaed of

Code: Select all

while(!cin.eof()) { 
cin>>i>>j; 
if (i<j) 
cout<<i<<" "<<j<<" "<<max_cyclic(i,j)<<endl; 
else 
cout<<i<<" "<<j<<" "<<max_cyclic(j,i)<<endl; 
} 
return 0; 
} 

[diego andres de barros]

the input is one one or with while.....
what is wrong????????
#include<stdio.h>


int main(){

long long int i=0,j=0,p,ma,me,k,x=0,y=0;

while( scanf("%lld %lld",&i,&j) ){
if(i>=j){
ma=i;
me=j;
}
else {
ma=j;
me=i;
}
p=me;
for(;p<=ma;p++){
k=p;
while(k>1){
if(!(k%2))k/=2;
else k= 3*k+1;
x++;
}
if(k==1)x++;
if(x>y)y=x;
x=0;
}
printf("%lld %lld %lld\n",i,j,y);
y=0;
}
return 0;
}
thanks!!!

[Landertxu]

This is my WA:

Code: Select all

#include <stdio.h>

int tabla[60000];

int cycle(unsigned long n)
{
    int c;
    if (n==1)
        c=1;
    else
        if (n<60000)
            if (tabla[n]!=-1)
               c=tabla[n];
            else
            {
                if (n%2==0)
                    c=cycle(n/2)+1;
                else
                    c=cycle(3*n+1)+1;
                tabla[n]=c;
            }
        else
            if (n%2==0)
                c=cycle(n/2)+1;
            else
                c=cycle(3*n+1)+1;
            
    return c;
}

int cmax(unsigned long i, unsigned long j)
{
    int maxim=cycle(i);
    int aux;
    unsigned long k;
    if (i>j)
    {
        aux=j;
        j=i;
        i=aux;
    }
    for (k=i+1;k<=j;k++)
    {
        aux=cycle(k);
        if (aux>maxim)
           maxim=aux;
    }
    return maxim;
}

int main()
{
    register int l;
    unsigned long i,j;
    for (l=2;l<60000;l++)
        tabla[l]=-1;
    tabla[1]=1;
    while (2==scanf("%u %u",&i,&j))
    {
        printf("%u %u %d\n",i,j,cmax(i,j));
    }
    return 0;
}

Do you have more test cases for seeing what is wrong?

[emotional blind]

TRY this inputs

Code: Select all

4 3
3 4

your program produces different maximum cycle length!

[taskin]

i dont understand what's ur problem, wa or tle? if tle, then try to store the values without recompute every time.

[vinit_iiita]

WHY TLE???

Code: Select all

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int a,b;
    while (cin>>a>>b)
    {
          int e,f;
          int c=0;
          if(b>a)
          { e=b;
            f=a;
          }
          else
          { e=a;
             f=b;
          } 
          for (int n=f;n<=e;n++)
          {   
              int s=0;
              int i;
              i=n;
              while (i!=1)
              {
                 if (i%2==1)
                 {i=i+i+i+1;
                  s++;} 
                 else 
                { i=i/2;
                 s++;
                 }
                 }
              if (s>c)
              c=s;
              s=0;

              }   
              c+=1;
          cout<<a<<" "<<b<<" "<<c<<endl;
          }                  
          return 0;
          }

plzzz help me out ......how to do it fast[/b]

[Rocky]

more i/o....
try this..
Input:

Code: Select all

20 20
9999 9999
1 9999
340 3000
3000 340
500 101
1 1
9999 9998

output:

Code: Select all

20 20 8
9999 9999 92
1 9999 262
340 3000 217
3000 340 217
500 101 144
1 1 1
9999 9998 92

Good Luck
Rocky

[Rale]

I don't understand how long do I read input.

I apologise if the question has already been asked, but I simply don't understand it. Here is my code, if it helps:

Code: Select all

#include <stdio.h>

int cycle (int n) {
	int i=0;
	while (n>0) {
		i++;
		if (n==1) break;
		if (n%2 == 1) n=3*n +1;
		else n=n/2;
			 }
return i;
}


int main () {

int n1,n2,i,max,l=0,a[10000],f,g,p;



while (scanf ("%d %d\n", &n1, &n2)!=EOF) {

if (n2<n1) {
	f=n1;
	g=n2;
}
else {
f=n2;
g=n1; 
}

	max = cycle(i);
  	for (i=g;i<=f;i++) {
	l=cycle(i);
	if (l>max) max=l;
}


printf ("%d %d %d",n1,n2,max);

	
}

return 0;

}

Does anyone know what's wrong with my code, and how long should the input be?

[diego andres de barros]

my problems is wa.....
i believe the input is wrong.........
see ,please !!!!!!!!!

[emotional blind]

my problems is wa.....
i believe the input is wrong.........
see ,please !!!!!!!!!

your program gets tle,

change this line

Code: Select all

while( scanf("%lld %lld",&i,&j) ){ 

to

Code: Select all

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

after getting ACCEPTED dont forget to REMOVE your code from here

[Rocky]

for input youyr code is ok but i make some change to your code and gives ok (accc),...
see this....

Code: Select all

max = cycle(0);  //always took the length of 0 as minimum
     for (i=g;i<=f;i++) { 
   l=cycle(i); 
   if (l>max) max=l; 
} 


printf ("%d %d %d\n",n1,n2,max); 

Good Luck
Rocky