100 - The 3n + 1 problem

[Eduard]

ok it'c for C but i'm using Pascal.

[Subeen]

long int works fine (I got AC using long int in C++). and no need for array.

[Six of Three]

I used a workaround for the problem in PASCAL, combining 2 longints and thus emulating 48bit integers which were long enough.
I wonder if you could use the (AFAIK) 64bit integer type "comp", which I think is only part of Borland (Turbo) Pascal. Is there a similar integer type in freepascal?

[little joey]

You'd better install free pascal if you want to solve more problems.
There are two 64-bit integer types Int64 (signed) and QWord (unsigned), but you don't need them for this problem; standard integer (32-bit, signed) is enough.

[Six of Three]

You'd better install free pascal if you want to solve more problems.

I see there are good arguments for doing so

There are two 64-bit integer types Int64 (signed) and QWord (unsigned), but you don't need them for this problem; standard integer (32-bit, signed) is enough.

Are you sure? I know it worked for the old 100.000-problem, but programs using the standard algorithm shown in the sample program do not seem to work with the new one.

[Eduard]

Dear friends i find another solution for problem 100 and i got accepted.
if the number n mod 2 <>0 then i'm not doing like this n*3+1 then it div 2.
i'm using an algoritm which find for n (n*3+1) div 2 without doing it and so i don't get a very big numbers.if someone whant to know my algoritm i can tel you.

[Six of Three]

Huh, this sounds like the incredible n:=n+n shr 1+1 tweak which delays the crashing point by some numbers. Arr... guess you did not mean that, it would be way too easy.
Finding (n*3+1)div 2 without "doing it"... sounds a little bit lunatic. I am glad there is another insane here

I think I should try the unsigned int from Freepascal, perhaps only this one bit is needed

[Eduard]

ok this is my solution.(my solution is for odd n)
for 1 (1*1+1)div 2 =2
for 3 (3*3+1)div 2 =5
for 5 =8
for 7 =11
for 9 =14
for 11 =17
...................................
...................................
...................................
it is not hard to sea that
2+3=5
5+3=8
8+3=11
11+3=14
14+3=17
it is progresia for which a[1]=2 and d=3
now this is the formuly which find for n (n*3+1) div 2
2+(((n+1) div 2)-1)*3
i whant to tell you that
2+(((n+1) div 2)-1)*3= (n*3+1) div 2

[playerX]

optimization, algorithmic and io

[Six of Three]

Your formula is the same as mine, only a few more brackets
Guess you have made some other optimization which prevents from computing these numbers which do not fit in Int32. Or which data type do you use?

Hmm... I think Int64 and similar fits best here

[Morning]

Code: Select all

/* @JUDGE_ID: 88826AB 100 C++ "THE 3N+1 PROBLEM" */
#include<stdio.h>
void main()
{
	long i,bi,min,max;
	int length,maxlength;
	while(1)
	{
		scanf("%ld %ld",&min,&max);
		printf("%ld %ld",min,max);
		maxlength=1;
		for(i=max;i>=min;i--)
		{
			length=1;
			//printf(" %d",max);
			bi=i;
			while(i!=1)
			{
				
				if(i%2==1) 
				{
					length+=1;
					i=i*3+1;
					//printf(" %d",i);
				}
				if(i%2==0)
				{
					length+=1;
					i=i/2;
					//printf(" %d",i);
				}
			}
			//length+=1;
			//printf("over\n");
			
			if(length>maxlength) maxlength=length;
			i=bi;
		}
		printf(" %d\n",maxlength);
	}
}

it said "01935883_24.c:44: syntax error before character 0323"
what does it mean?

[Eduard]

i use longint in pascal it's 4 byte(32 bit)

[Subeen]

replace your '//' style comments with '/* */' style comments. then there will be no compile error in your code.

But then u will get TLE cause ur program never terminates.
while(1)

and after fixing this u will get TLE again cause...

[Morning]

yeah,now i can solve the problem,thank u indeed

[Morning]

i'm sorry,but i still got complie error message

Code: Select all

#include<stdio.h>
void main()
{
	long i,bi,min,max,temp;
	int length,maxlength;
	while(1)
	{
		
		printf("%ld %ld",min,max);
		maxlength=1;
		
		if(max<min)
		{
			temp=max;
			max=min;
			min=temp;
		}
		
		for(i=max;i>=min;i--)
		{
			length=1;
			bi=i;
			
			while(i!=1)
			{
				
				if(i%2==1) 
				{
					length+=1;
					i=i*3+1;
				}
				if(i%2==0)
				{
					length+=1;
					i=i/2;
				}
			}
			
			if(length>maxlength) 
				maxlength=length;
			i=bi;
		}
		
		printf(" %d\n",maxlength);
	}

[/code]