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

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

Post by 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
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

Post by 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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

Regards
Dominik

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

that is not true.

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

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

Post by 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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

tabo
New poster
Posts: 2
Joined: Fri Sep 20, 2002 7:05 pm
Contact:

ranklist question

Post by 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
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank »

use a very efficient algorithm.

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by 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
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

mklein49
New poster
Posts: 5
Joined: Mon Sep 23, 2002 1:56 am

More 100 troubles

Post by 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
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by 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
New poster
Posts: 5
Joined: Mon Sep 23, 2002 1:56 am

Post by 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
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:

appropriate place

Post by Shahid »

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

isn't it?

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

Post by 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
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by 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.

Post Reply

Return to “Volume 1 (100-199)”