694  The Collatz Sequence
Moderator: Board moderators

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

 New poster
 Posts: 45
 Joined: Fri Jan 16, 2004 7:02 pm
 Location: CSE::BUET
 Contact:
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.
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!!!!

 New poster
 Posts: 45
 Joined: Fri Jan 16, 2004 7:02 pm
 Location: CSE::BUET
 Contact:
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
OUTPUT
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
Collatz Problem
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
I can get the time down to 1.7 seconds but how do you guy get the time down to 0
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;
}
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>((L1)/3))break;
else {A=A*3+1;terms++;}
}
}
cout<<"Case "<<Case<<": A = "<<mainA<<", limit = "<<L<<", number of terms = "<<terms<<endl;
cin>>A>>L;
}
}
Hi, farzane!
"mainA=A;" must in your while loop.
I mean,
"mainA=A;" must in your while loop.
I mean,
Code: Select all
...
while(A>0){
mainA=A;
...
}
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?
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?