Page 8 of 93

100 - 3n+1 Problem (SIGSEGV!!!! It can't be!)

Posted: Tue Aug 27, 2002 8:16 pm
by 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;
}

Posted: Tue Aug 27, 2002 8:46 pm
by Adrian Kuegel
You didn't change your code, but the program has changed. Read the description again :-)

problem100

Posted: Wed Sep 04, 2002 3:14 pm
by katy
I don't konw what the problem is in my code.
Can any one help me? :cry:

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!!!!

sorry!

Posted: Wed Sep 04, 2002 3:39 pm
by katy
I'm sorry!
I should told you that the result I got is "time limit exceeded". :-?

Posted: Wed Sep 04, 2002 4:06 pm
by hank
your code is very inefficient.

Posted: Wed Sep 04, 2002 4:51 pm
by katy
so,what can I do to get it better?

i found something

Posted: Thu Sep 05, 2002 3:46 am
by Sasko
your program is not doing anything if i=j

some hints

Posted: Tue Sep 10, 2002 1:42 am
by 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. :wink:

Posted: Tue Sep 10, 2002 2:22 am
by 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 :)

Posted: Tue Sep 10, 2002 3:12 am
by 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 :o

[please help me]---Problem 100

Posted: Fri Sep 13, 2002 9:01 pm
by 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;
	}
}


Posted: Sat Sep 14, 2002 11:40 am
by 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

picard thank you very much!!!

Posted: Sat Sep 14, 2002 12:58 pm
by samuelcdf
Thank you very much!!!
My head is big, but I am stupid...... haha~~~ ^^a

help p100

Posted: Sun Sep 15, 2002 11:21 am
by eureka
why my code is compile error.
who can help me :x

#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;

}

(a) few thoughts

Posted: Sun Sep 15, 2002 6:57 pm
by 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. :roll: