694 - The Collatz Sequence

[jackie]

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]

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!]

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

[Heartattack!]

Johny,
You don't need a space before the "Case". I just got AC without it.

[_.B._]

Thanks H!
Had some other error too.

Keep posting!

[Sedefcho]

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

[farzane]

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!]

Hi, farzane!

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

I mean,

Code: Select all

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

[WR]

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?

[Jan]

Try my formatting...

Code: Select all

"Case %d: A = %d, limit = %d, number of terms = %d\n"

Hope it helps.

[WR]

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 (:().

[Jan]

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

[scott1991]

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

[Jan]

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.

[Kikuneechan]

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~