## 694 - The Collatz Sequence

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

Moderator: Board moderators

### 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?!..
Melon Melon
New poster

Posts: 17
Joined: Fri May 31, 2002 6:30 pm

### Overflow

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

-novice
Fresh
New poster

Posts: 46
Joined: Mon Apr 15, 2002 10:42 am

### huh?

I used brute force all the way and got Accepted.

Regards,
ec3_limz
ec3_limz
Learning poster

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

### 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;
}
Red Scorpion
Experienced poster

Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

### 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]
ttwu
New poster

Posts: 8
Joined: Tue May 13, 2003 4:31 pm

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.

cytse
Learning poster

Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong

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

Posts: 8
Joined: Tue May 13, 2003 4:31 pm

### 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)
Thiago Serra
New poster

Posts: 3
Joined: Sun Oct 05, 2003 1:32 pm
Location: Campinas-SP

### 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.
zack
New poster

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

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

Input:
Code: Select all
`1 12147483647 11 21474836472 21474836472147483647 22147483647 214748364214748364 21474836471 0-3 -2`

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

Hope these'll help!
[Tanzim Saqib]
-----------------------------
Problemsetter of 10490
Website: http://tanzim.tk
Tanzim-Saqib
New poster

Posts: 10
Joined: Thu Jun 05, 2003 5:23 pm
Location: CS, AIUB, Dhaka, Bangladesh

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

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

Shaka_RDR
New poster

Posts: 23
Joined: Sat Oct 04, 2003 12:12 pm
Location: in Your Heart ^^

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

Posts: 10
Joined: Thu Jun 05, 2003 5:23 pm
Location: CS, AIUB, Dhaka, Bangladesh

### Need help.

Greetings!.
Is this I/O allright?:
Input:
Code: Select all
`715827883 2147483647715827882 2147483647715827881 2147483647-2 -3`

Otput:
Code: Select all
`Case 1: A = 715827883, limit = 2147483647, number of terms = 1Case 2: A = 715827882, limit = 2147483647, number of terms = 33Case 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.
[color=darkgreen][b]_.

_.B._
Experienced poster

Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela

Next