694 - The Collatz Sequence

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

Moderator: Board moderators

Melon Melon
New poster
Posts: 17
Joined: Fri May 31, 2002 6:30 pm
Contact:

694 ~ The Collatz Sequence

Post by Melon Melon » Wed Jul 10, 2002 7:29 am

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

Fresh
New poster
Posts: 46
Joined: Mon Apr 15, 2002 10:42 am
Contact:

Overflow

Post by Fresh » Thu Jul 11, 2002 9:12 am

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

-novice

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

huh?

Post by ec3_limz » Mon Aug 12, 2002 6:19 pm

I used brute force all the way and got Accepted.

What's your algo?

Regards,
ec3_limz

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

WA 694 (The Collatz Sequence)

Post by Red Scorpion » Sat Dec 14, 2002 4:57 am

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
New poster
Posts: 8
Joined: Tue May 13, 2003 4:31 pm

694 - The Collatz Sequence

Post by ttwu » Sat May 24, 2003 7:21 am

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]

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Sat May 24, 2003 11:53 am

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
New poster
Posts: 8
Joined: Tue May 13, 2003 4:31 pm

Post by ttwu » Sat May 24, 2003 4:47 pm

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

Thiago Serra
New poster
Posts: 3
Joined: Sun Oct 05, 2003 1:32 pm
Location: Campinas-SP
Contact:

694

Post by Thiago Serra » Wed Oct 08, 2003 7:22 pm

Please, I need some extra test cases for my program!!!!
"Dust in the wind... Everything is dust in the wind"(Kansas)
"Hay que endurecer, pero sin perder la ternura jamas!"(Che Guevara)

zack
New poster
Posts: 9
Joined: Sun Oct 12, 2003 2:08 am

694 output

Post by zack » Sun Oct 19, 2003 7:54 pm

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.
Last edited by zack on Sun Oct 19, 2003 8:23 pm, edited 1 time in total.

zack
New poster
Posts: 9
Joined: Sun Oct 12, 2003 2:08 am

Post by zack » Sun Oct 19, 2003 8:22 pm

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
New poster
Posts: 10
Joined: Thu Jun 05, 2003 5:23 pm
Location: CS, AIUB, Dhaka, Bangladesh
Contact:

Post by Tanzim-Saqib » Mon Oct 27, 2003 9:11 pm

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!
[Tanzim Saqib]
-----------------------------
Problemsetter of 10490
Website: http://tanzim.tk

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Thu Oct 30, 2003 3:23 am

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


}
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

User avatar
Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:

Post by Shaka_RDR » Thu Oct 30, 2003 3:36 am

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..... :)
Every person exists for another person. and that person exists for the other one. it's just the matter of existence...
May every person helps each other and creates a world full of joy...

Tanzim-Saqib
New poster
Posts: 10
Joined: Thu Jun 05, 2003 5:23 pm
Location: CS, AIUB, Dhaka, Bangladesh
Contact:

Post by Tanzim-Saqib » Thu Oct 30, 2003 6:28 pm

You know what... Practice makes a man perfect! :D
[Tanzim Saqib]
-----------------------------
Problemsetter of 10490
Website: http://tanzim.tk

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Need help.

Post by _.B._ » Sat Apr 17, 2004 2:32 am

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!.
_.

Post Reply

Return to “Volume 6 (600-699)”