100 - The 3n + 1 problem

[Vartanov Daniel]

6 monthes ago i got AC for this problem!!!
I posted this problem again several hours ago and got SIGSEGV, but i DID NOT change my code!!!

Code: Select all

#include <stdio.h>
#include <string.h>

long sol[10001];

void precount()
{
  long t;
  long c;
  for (long i = 1; i <= 10000; i++)
  {
    c = 0;
    t = i;
    while (t != 1)
    {
      if (t % 2) t = 3 * t + 1; else t /= 2;
      c++;
    }
    sol[i] = c;
  }
}

int main()
{
  int n, m, p, q;
  long max = 0;
  precount();
  while (scanf("%d %d", &n, &m) == 2)
  {
    max = 0;
    if (m>n)
    {
      p = n;
      q = m;
    }
    else
    {
      p = m;
      q = n;
    }
    for (int i = p; i <= q; i++)
      if (sol[i] > max) max = sol[i];
    printf("%d %d %ld\n", n, m, ++max);
  }
  return 0;
}

[Adrian Kuegel]

You didn't change your code, but the program has changed. Read the description again :-)

[katy]

I don't konw what the problem is in my code.
Can any one help me?

Code: Select all

#include<stdio.h>
int lengh(long int);
int main(void)
{
  long int i,j,a;
  int k,c;
    while(1)
     {
      c=0;
      scanf("%ld %ld",&i,&j);
      if(i==0||j==0)
	break;
      if(i>j)
	{
	  for(a=j;a<=i;a++)
	{  k=lengh(a);
	   if(k>c)
	   c=k;
	}
      printf("%ld %ld %d\n",i,j,c);
	}
      else
      {
	for(a=i;a<=j;a++)
	  {  k=lengh(a);
	     if(k>c)
	     c=k;
	  }
	printf("%ld %ld %d\n",i,j,c);
       }
     }
    return 0;
}
int lengh(long int n)
{
  int b=1;
  if(n==1)
    return 1;
  while(n>1)
  {
    if(n%2==1)
      n=3*n+1;
    else
      n=n/2;
    b=b+1;
  }
  return b;
}

Thanks!!!!

[katy]

I'm sorry!
I should told you that the result I got is "time limit exceeded".

[hank]

your code is very inefficient.

[katy]

so,what can I do to get it better?

[Sasko]

your program is not doing anything if i=j

[zbogi]

There is one very common error on this task: preasuming that a<=b it is not true if I remember right.
As fas as having a faster code - may be you could save an array with already computed values. E.g. you will compute length(10) once for 10 10, and one more time for 1 15. That is very stupid for multi input tasks.
Good luck next time.

[arc16]

for more faster code, you could also minimize the calculation progress, by not calculating all the number.
remember:
if cycle[n] = a, then cycle[2n] = a+1, and so on...
using sieve-like technique, you could precalc all the possible number with just a little time

[ithamar]

I think that the optimization required for this problem is not that hard. I got AC in this problem without taking too much care about optimization. The only thing is that i use DP, explicitly Memoization.

Hope this can help.

PS: Before rejudgment simple code like the one you posted was AC, but not anymore

[samuelcdf]

please help me to point out my code wrong. I try much times, but still can find the error ><~~

Code: Select all

#include <stdio.h>
#include <stdlib.h>
	
void main(void)
{
                unsigned long i=0L, input_i=0L, j=0L, max=0L;
	unsigned long counter=0L, temp=0L;

	while(scanf("%lu %lu", &i, &j)==2)
	{
		if(i>j)
		{
			temp=i;
			i=j;
			j=temp;
		}
		for(input_i=i;i<=j;i++)
		{
			temp=i;
			counter=1L;
			while(temp!=1)
			{
				if(temp%2==0)
				{
					temp/=2;
				}
				else
				{
					temp=(3*temp)+1;
				}
				counter++;
			}
			if(counter>max)
				max=counter;
		}
		printf("%lu %lu %lu\n", input_i, j, max);
		max=0;
	}
}

[Picard]

when i>j you swap i,j but in the output you should print the i,j pair in the original order as in input

[samuelcdf]

Thank you very much!!!
My head is big, but I am stupid...... haha~~~ ^^a

[eureka]

why my code is compile error.
who can help me

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

int main()
{

long n[10001];

long i,j;

long count,len,a ;



for (long p = 1;p<=10000;p++)
{



n[p] = 1;
len = 1;
a = p;



while (a!=1)
{

if (fmod(a,2) == 1)

a = 3*a + 1 ;

else

a = a/2;

len++;




}

n[p] = len;

}


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

{
count = n;

for (int k = i;k<=j;k++)
{
if (n[k] > count)
count = n[k];
}
printf("%ld %ld %ld\n",i,j,count);

}
return 0;

}

[zbogi]

First are you sure you send it az C++, not as a C code.
Second this variable count. I am not sure but if it is doubled in the compiler as a reserved word there may be trouble.
And last, but not least It would be great if pasted and the errors the jusge returned to you. See, normally(if option not switched off) it will send you a letter with subject "Compile error". In its body there will be written the rrors occured during compilation.
If you still have problems post back the errors.