100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Vartanov Daniel
New poster
Posts: 5
Joined: Tue Aug 27, 2002 7:46 pm
Location: Russia
Contact:

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

Post 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;
}

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

katy
New poster
Posts: 3
Joined: Tue Sep 03, 2002 4:40 pm
Contact:

problem100

Post 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!!!!
Last edited by katy on Wed Sep 04, 2002 4:45 pm, edited 1 time in total.

katy
New poster
Posts: 3
Joined: Tue Sep 03, 2002 4:40 pm
Contact:

sorry!

Post by katy »

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

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank »

your code is very inefficient.

katy
New poster
Posts: 3
Joined: Tue Sep 03, 2002 4:40 pm
Contact:

Post by katy »

so,what can I do to get it better?

Sasko
New poster
Posts: 3
Joined: Tue Sep 03, 2002 3:31 am

i found something

Post by Sasko »

your program is not doing anything if i=j

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

some hints

Post 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:
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post 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 :)

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post 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
Those Who Don't Know History are doomed to repeat it

samuelcdf
New poster
Posts: 3
Joined: Tue Dec 04, 2001 2:00 am
Contact:

[please help me]---Problem 100

Post 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;
	}
}


Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post 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

samuelcdf
New poster
Posts: 3
Joined: Tue Dec 04, 2001 2:00 am
Contact:

picard thank you very much!!!

Post by samuelcdf »

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

eureka
New poster
Posts: 5
Joined: Sun Sep 15, 2002 11:15 am

help p100

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

}

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

(a) few thoughts

Post 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:
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

Post Reply

Return to “Volume 1 (100-199)”