694 - The Collatz Sequence

[Melon Melon]

I got time limited exceed...
..
would anyone give me some test cases..pls?!..
or...the possible reasons..cause the time limited exceed...pls?!..

[Fresh]

Try use 'long long' declaration, ((10^9) * 3 + 1) > MAX_INT

-novice

[ec3_limz]

I used brute force all the way and got Accepted.

What's your algo?

Regards,
ec3_limz

[Red Scorpion]

Can anyone help me, I got WA for this problem.

I use an unsigned long int (C++), and to limited 'a', i use this expression :

count = 0;
while (a<=l) { //a = number, l = limit
count++;
if (a==1) break;
else if (a%2) {
if (a>715827882) break;
else a=a*3+1;
}
else a/=2;
}

[ttwu]

I got output limit exceeded but I don't know why..
please help me..Thanks!

[cpp]
#include<stdio.h>
void main()
{
unsigned long i,j;
int clen,setnum=1;

while(1)
{
scanf("%ld %ld",&i,&j);
if (i<0 && j<0) break;

printf("Case %d: A = %ld, limit = %ld, number of terms = ",setnum,i,j);

for (clen=1;i!=1;clen++)
{
if (i%2!=0) { i=3*i+1; }
else { i=i/2; }
if (i>j) break;
}

printf("%d\n",clen);
setnum++;
}

}
[/cpp]

[cytse]

i,j are defined as unsigned long, so their values are always non-negative. Therefore "(i<0 && j<0)" is always false. There is no way to break the infinite loop.

[ttwu]

I made some changes to the code and got accepted
It was the negative problem. Thanks very much!

[Thiago Serra]

Please, I need some extra test cases for my program!!!!

[zack]

Working on 694. Running locally, the output isn't the expected (as presented on the problem descrip. page). Some examples:

3 100
expected: 8
program: 8

34 100
expected: 14
program: 14

75 250
expected: 3
program: 4 WRONG

101 304
expected: 26
program: 26

101 303
expected: 1
program: 2 WRONG

Also, when uploading to the server, it gets TLE.

[zack]

Just fixed the problem related to the wrong output in those test cases (checking a > l too soon).

Still gets TLE anyways.

Using
while not eof (input) do

as...

input line one
-- output result
input line two
-- output result
input ...
-- output result

Also tried while a > 0 TLE also.

[Tanzim-Saqib]

This one is very simple and pretty straight forward 3n+1 problem. Now try these...

Input:

Code: Select all

1 1
2147483647 1
1 2147483647
2 2147483647
2147483647 2
2147483647 214748364
214748364 2147483647
1 0
-3 -2

Output:

Code: Select all

Case 1: A = 1, limit = 1, number of terms = 1
Case 2: A = 2147483647, limit = 1, number of terms = 1
Case 3: A = 1, limit = 2147483647, number of terms = 1
Case 4: A = 2, limit = 2147483647, number of terms = 2
Case 5: A = 2147483647, limit = 2, number of terms = 1
Case 6: A = 2147483647, limit = 214748364, number of terms = 1
Case 7: A = 214748364, limit = 2147483647, number of terms = 184
Case 8: A = 1, limit = 0, number of terms = 1

Hope these'll help!

[Shaka_RDR]

strange.... i still have WA
i've cheked my code using that input, and the output is exactly the same... any body can help me ? here is my code

Code: Select all

#include <stdio.h>

void main()
{
	long long int begin,limit,a,sequence,no=0;
	#ifndef ONLINE_JUDGE
		freopen ("694.in","r",stdin);
		freopen ("694.out","w",stdout);
	#endif

	while (scanf ("%ld %ld ",&begin, & limit)!=EOF)
	{
		if (begin<0 && limit <0) break;

		no++;
		a=begin;
		sequence=1;

		while (a!=1)
		{


			if (a%2==0)
			{
				a/=2;

			}
			else
			{
				a =  3*a+1;

			}

			if (a>limit) break;
			sequence++;

		}

		printf ("Case %lld: A = %lld, limit =  %lld, number of terms = %lld\n",no,begin,limit,sequence);
	}


}

[Shaka_RDR]

sorry.... i got AC (PE) now... only 30 second after i post my previous message i found my mistake....

i use scanf("%ld") for a long long integer data type...... it should be %lld...


its my second mistake about using long or long long data type.... i wonder how could i be so careless? btw, thanx for that sample I/O... it helps me a lot.....

[Tanzim-Saqib]

You know what... Practice makes a man perfect!

[_.B._]

Greetings!.
Is this I/O allright?:
Input:

Code: Select all

715827883 2147483647
715827882 2147483647
715827881 2147483647
-2 -3

Otput:

Code: Select all

Case 1: A = 715827883, limit = 2147483647, number of terms = 1
Case 2: A = 715827882, limit = 2147483647, number of terms = 33
Case 3: A = 715827881, limit = 2147483647, number of terms = 5

I've tried all I/O I've seen in this forum, but still get WA.
If I/O is good, I'll try posting the code.
Thanks in advance!.