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

It is a simple problem.
But the test data may be reach the limit.
so you'd better use the long long int not the int
jackie
New poster

Posts: 47
Joined: Tue May 04, 2004 4:24 am

printf ("<need one space> Case %lld: A = %lld, limit = <you add more space>%lld, number of terms = %lld",no,begin,limit,count);

i found the error look at space
jhonny_yang
New poster

Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

### Re: Need help.

_.B._,
You say:
Case 3: A = 715827881, limit = 2147483647, number of terms = 5

In this case, the number of terms should be 6.
1. 715827881*3 + 1 = 2147483644
2. 2147483644/2=1073741822
3. 1073741822/2=536870911
4. 536870911*3 + 1=1610612734
5. 1610612734/2=805306367
6. 805306367*3 + 1=2415919102>limit

You gotta count all the steps.
Hope it helps.
Last edited by Heartattack! on Tue Nov 30, 2004 10:10 pm, edited 1 time in total.
We will, We will BREAK LOOP!!!!
Heartattack!
New poster

Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET

Johny,
You don't need a space before the "Case". I just got AC without it.
We will, We will BREAK LOOP!!!!
Heartattack!
New poster

Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET

### Re: Need help.

Thanks H!
Had some other error too.

Keep posting!
[color=darkgreen][b]_.

_.B._
Experienced poster

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

### SAMPLE IO

For anyone who might be interested here is some
sample I/O ( from an ACC program of course ).

It includes the 3 test cases posted above by _.B._

INPUT

Code: Select all
`3 100 34 100  75   250 27   2147483647 101 304 101 303 715827883 2147483647 715827882   2147483647 715827881 21474836472000 10000000131003 10000000199999  50000000199999 190100000199999 214100000199997 21410000017771 21410000017773 214100000377799 2141900 -2 -4`

OUTPUT

Code: Select all
`Case 1: A = 3, limit = 100, number of terms = 8Case 2: A = 34, limit = 100, number of terms = 14Case 3: A = 75, limit = 250, number of terms = 3Case 4: A = 27, limit = 2147483647, number of terms = 112Case 5: A = 101, limit = 304, number of terms = 26Case 6: A = 101, limit = 303, number of terms = 1Case 7: A = 715827883, limit = 2147483647, number of terms = 1Case 8: A = 715827882, limit = 2147483647, number of terms = 33Case 9: A = 715827881, limit = 2147483647, number of terms = 6Case 10: A = 2000, limit = 100000001, number of terms = 113Case 11: A = 31003, limit = 100000001, number of terms = 161Case 12: A = 99999, limit = 500000001, number of terms = 227Case 13: A = 99999, limit = 1901000001, number of terms = 227Case 14: A = 99999, limit = 2141000001, number of terms = 227Case 15: A = 99997, limit = 2141000001, number of terms = 90Case 16: A = 7771, limit = 2141000001, number of terms = 115Case 17: A = 7773, limit = 2141000003, number of terms = 40Case 18: A = 77799, limit = 2141900, number of terms = 39`

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

I'm getting WA.Could anyone tell me why?
Code: Select all
`#include<iostream.h>//#include<fstream.h>void main(){   //ifstream cin("694.in");   long long A,L,terms,Case,mainA;   cin>>A>>L;   Case=0;   mainA=A;   while(A>0){      Case++;      terms=1;      while(true){         if(A==1)break;         if(A%2==0){A/=2;terms++;}         else{            if(A>((L-1)/3))break;            else {A=A*3+1;terms++;}         }      }      cout<<"Case "<<Case<<": A = "<<mainA<<", limit = "<<L<<", number of terms = "<<terms<<endl;      cin>>A>>L;   }}`
farzane
New poster

Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Hi, farzane!

"mainA=A;" must in your while loop.

I mean,

Code: Select all
`...while(A>0){   mainA=A;   ...   }`
hi!man!
New poster

Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

### P.E. problem 694

What can be the reason for a presentation error in the solution of problem 694??!!

There are no blank lines (according to the description), there's no multiple input/output.

I think I've already tried all possible combinations, including a leading space.

Any idea anybody?
WR
Experienced poster

Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Try my formatting...
Code: Select all
`"Case %d: A = %d, limit = %d, number of terms = %d\n"`

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

### 694 P.E.

Thanks a lot, Jan!

It DID help. And special thanks for the fast response!!!

Care to share your knowledge?

The format specifier for a LONG variable is %ld, isn't it?
Why does %d work instead?

Needless to say, my results were ok, otherwise the verdict would have been a WRONG ANSWER (:().
WR
Experienced poster

Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

You are welcome. I used int (not long) because in uva's compiler (and mine, too) int and long both require 32bit. May be that's why both identifier work for both (int & long).
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

I'm getting tle and have no idea on making it faster...can someone help please?

Code: Select all
`#include<iostream>int main(){         unsigned int start, max, terms=1,test=1,A;a:   scanf("%u %u",&start,&max);      if(start<0&&max<0)      {return 0;}      else      {         A=start;      while(start<=max&&start!=1)      {         start = (start&1)==0?(start>>1):(start*3+1);         terms++;      }      printf("Case %u: A = %u, limit = %u, number of terms = %u\n",test,A,max,terms);      test++;terms=1;      goto a;      }}`
scott1991
New poster

Posts: 28
Joined: Fri Dec 07, 2007 11:41 pm

Both start and end are unsigned integers. So, you will not find -1 in the input. I mean if the input is -1 -1, then start and max both will be unsigned(-1) = 4294967295.
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

### Re: 694 - The Collatz Sequence

Heya. I'm doing this in Java. I've coded everything and everything prints out as the page says so, but I get TIme Limit Exceeded which is really aggravating.

Code: Select all
`import java.util.Scanner;class Main {  public static void main(String[] args) {    Scanner fred = new Scanner(System.in);    int start;    int limit;    int terms;    int a = 0;        while (fred.hasNext()) {      start = fred.nextInt();      limit = fred.nextInt();      if (start > 0) {        terms = getLength(start, limit);        a++;      } else {        break;      }      System.out.println("Case "+a+": A = "+start+", limit = "+limit+", number of terms = "+terms);    }  }    public static int getLength(int x, int y) {    int length = 1;    while (x != 1) {      if (x <= y) {        if ( x % 2 == 0) {          x = x / 2;          length++;        }else{          x = x * 3 + 1;          length++;        }      } else {        length--;        break;      }    }        return length;  }}`

Thankies~
Kikuneechan
New poster

Posts: 1
Joined: Sun Nov 01, 2009 10:06 pm

PreviousNext

Return to Volume VI

### Who is online

Users browsing this forum: No registered users and 1 guest