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

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

Post by jackie » Thu May 06, 2004 11:03 am

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

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

Post by jhonny_yang » Mon Nov 22, 2004 6:25 pm

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

Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

Re: Need help.

Post by Heartattack! » Tue Nov 30, 2004 10:08 pm

_.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 :evil: 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
Contact:

Post by Heartattack! » Tue Nov 30, 2004 10:09 pm

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

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

Re: Need help.

Post by _.B._ » Sat Dec 25, 2004 11:03 am

Thanks H!
Had some other error too.

Keep posting!
_.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

SAMPLE IO

Post by Sedefcho » Thu May 12, 2005 12:34 pm

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 2147483647
2000 100000001
31003 100000001
99999  500000001
99999 1901000001
99999 2141000001
99997 2141000001
7771 2141000001
7773 2141000003
77799 2141900
 -2 -4

OUTPUT

Code: Select all

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

B.E
New poster
Posts: 7
Joined: Tue May 24, 2005 5:20 am

Collatz Problem

Post by B.E » Thu May 26, 2005 11:00 am

is there a quicker way of working out the cycle length then the standard iteration technique.
I can get the time down to 1.7 seconds but how do you guy get the time down to 0

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Thu May 26, 2005 1:12 pm

Use memoization.

Regards
Sanny

B.E
New poster
Posts: 7
Joined: Tue May 24, 2005 5:20 am

Post by B.E » Thu May 26, 2005 2:48 pm

I tryed it but it was slower than before

nibbler
New poster
Posts: 22
Joined: Fri Jun 04, 2004 10:30 pm

Post by nibbler » Thu May 26, 2005 8:36 pm

why don't you post your code?

B.E
New poster
Posts: 7
Joined: Tue May 24, 2005 5:20 am

Post by B.E » Fri May 27, 2005 12:00 am

my code

Code: Select all

#include <stdio.h>
char *Format="%d %d";

int main() 
{ 
  int i,j; 
  register unsigned int tmp;
  register int current_length,Longest_Length; 
   while (scanf(Format,&i,&j)!= EOF)
  	{
			 Longest_Length = 0; 
    printf(Format,i,j);
   if (i > j) 
    { 
       i ^=j; 
       j ^=i; 
       i ^=j; 
    }
   if (j > 1000000)
   {
   	  	 return 1;
}
    for (;i <= j;i++) 
    { 
       tmp = i; 
       current_length = tmp < 3 ? tmp:2; 
       while (!(tmp < 3)) 
       { 
            if (tmp & 1)
            {
              //tmp = 3*tmp+1;
              __asm__ __volatile__("leal 1(%1,%1,2), %0" : "=q" (tmp)  : "0" (tmp) );
              
              current_length++;
		    }   
                   tmp >>= 1; 
                   current_length++;

       }              
       
         if (Longest_Length < current_length) 
             Longest_Length = current_length; 
   } 
   	 printf(" %d\n",Longest_Length);
}    
   
    return 0; 

}   


B.E
New poster
Posts: 7
Joined: Tue May 24, 2005 5:20 am

Post by B.E » Fri May 27, 2005 12:05 am

Prehaps maybe one of u guy can post some of your code

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Post by farzane » Wed Aug 23, 2006 10:25 am

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

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Fri Dec 29, 2006 1:37 pm

Hi, farzane!

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

I mean,

Code: Select all

...
while(A>0){
   mainA=A;
   ...
   }

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

P.E. problem 694

Post by WR » Wed Jan 10, 2007 12:54 pm

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?

Post Reply

Return to “Volume 6 (600-699)”