100 - The 3n + 1 problem

[pc5971]

Think at this problems:

1. What about this input line:

Code: Select all

10000 1

you didn't take this case...

2. I think that thay change the problem specifications and the limit it's not 10000...

3. What do you think about memorization of 1 to 200000 for example...

4. For improve your solution let's see an example:

20 -> 10 -> 5 -> ...

so len(20)=len(10)+1

Think at this...

I hope I could help you...

Carmen

[pc5971]

I fogot something:

I received several times an error if I tried to declare a variable in a for loop like your's:

[c]
for (long p = 1;p<=10000;p++)
[/c]

you need to declare all variabiles at the beginig of the function (or main) because they compile your program using ANSI C/C++...

Carmen

[Dominik Michniewski]

'count' isn't a reserved word ...
It maybe used as normally variable

Regards
Dominik

[zbogi]

you CAN do this : for (int i=10;i<20;i++) ...
if you write in C++
and you CANNOT in ANSI C
It is simple really.

As for the count word. It is possible not to be reserved, but I had this problem with other word, but I am not sure witch exactly. I really don`t wrire on DJGPP, the only way to be sure about is or isn`t is to compile it under the judge`s version.

[eureka]

thank everybody!

I have correct my code like this

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

int main()
{

long n[10001];

long i,j;

long cou,len,a ,temp;



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)

{
if (i>j)
{
temp = i;
i = j;
j = temp;
}
cou = n;

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

}
return 0;

}


send with c++


but judge say the error:

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.140 seconds

[Dominik Michniewski]

Limit for a and b is now 1 milion ... read carefully fixing notes )
And you have array to only 10000 elements .....

[tabo]

Hello,

Just curious as to how one can get 0:00:000 cpu time in the ranklist.. say for example problem 100(3n+1)...


tabo

[hank]

use a very efficient algorithm.

[Ivor]

One cannot get 0.000 time on 100 as far as I know. But the system has a timing glitch and so it happens that some people, including me, have been mistimed. There are a couple of posts in the misc section.

But generally you need a very good algorithm and/or IO routines,
Ivor

[mklein49]

Could somebody look at this code and tell me what the problem is? I can't seem to find anything wrong.

Code: Select all

[cpp]

/* @JUDGE_ID:   100 C++ */
/* @begin_of_source_code */

#include <iostream.h>
#include <stdio.h>


int cycle(int n);

int main()
{	
	int i, j, count, temp, n, max;

	count = 0;
	while(!(cin.eof()))
	{		
		cin >> i >> j;
		if (i > 0 && i < 1000000 && j > 0 && j < 1000000)
		{
			if (i > j)
			{
					temp = i;
					i = j;
					j = temp;
			}
			max = -100;	
			for (n = i; n <= j; n++)
			{
				temp = cycle(n);
				if (temp > max)
					max = temp;
			}
			cout << i << " " << j << " " << max << endl;
		}
	}
	return 0;
}


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

/* @end_of_source_code */

[/cpp]

[arc16]

Code: Select all

The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line). 

if input: 10 1, then output should 10 1 20

[mklein49]

I'm still getting an error. I modified my cycle algorithm to be recursive, too. I noticed that on a couple of numbers, ie 113383, if I try to caclulate the cycles, the number will be greater than 2^32. So, I'm not sure what to do.

[cpp]
/* @JUDGE_ID: 100 C++ */
/* @begin_of_source_code */

#include <iostream.h>

int cycle(int n);

int main()
{
int i, j, count, temp, m, n, max;

count = 0;
while(!(cin.eof()))
{
cin >> i >> j;
if (i > 0 && i < 1000000 && j > 0 && j < 1000000)
{
if (i > j)
{
n = i;
m = j;
}
else
{
m = i;
n = j;
}
max = -100;
for ( ; m <= n; m++)
{
temp = cycle(m);
if (temp > max)
max = temp;
}
cout << i << " " << j << " " << max << endl;
}
}
return 0;
}

int cycle(int n)
{
if (n == 1)
return 1;
else if (n % 2)
return cycle(3*n + 1) + 1 ;
else
return cycle(n/2) + 1;
}

/* @end_of_source_code */
[/cpp]

[Shahid]

i think for this kind of queries, the appropriate place is the misc section...

isn't it?

[arc16]

the only mistake i can find is for n = 55. Your output is 113 and the correct output is 114. Since f(2n) = f(n)+1, it will affects the result of 110,220,440,etc as well. you should try to debug your program using those input and find your mistake.
good luck

[Picard]

the problem is not in cycle() (cycle(55)==113 is good). you repeat the last test case, use "while (cin >> i >> j)" instead. btw don't worry about integer overflow in cycle() the problem description states it won't happen.