## 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

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

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?

I used brute force all the way and got Accepted.

Regards,
ec3_limz

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

### WA 694 (The Collatz Sequence)

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

I got output limit exceeded but I don't know why..

[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
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
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
I made some changes to the code and got accepted
It was the negative problem. Thanks very much!

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

### 694

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

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
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:
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

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:
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...

Shaka_RDR
New poster
Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^
Contact:
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:
You know what... Practice makes a man perfect!
[Tanzim Saqib]
-----------------------------
Problemsetter of 10490
Website: http://tanzim.tk

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

### Need help.

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.