UVa : 100 (The 3n + 1 problem)


Statement

http://uva.onlinejudge.org/external/1/100.html

Tricky Lines

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

You can assume that no operation overflows a 32-bit integer.

The integers i and j must appear in the output in the same order in which they appeared in the input

Gotcha

  • Integer data type could be enough for this problem.
    But the interim process might not go well with integers.
    For instance, 827370449 is an Integer and odd number.
    3 * 827370449 + 1 = 2482111348 won’t fit into an integer.
  • first number i can be greater than j
  • Preserve the input sequence in output.

Critical Input

1 1
10 1
210 201
113383 113383
999999 1

Critical Output

1
10 1 20
210 201 89
113383 113383 248
999999 1 525

Runtime

0.980s

Faster solution

  • use bitwise operation (#29)
  • n >>= 1;
    // or
    n = n >> 1;
    // is much faster than
    n = n / 2;
    // or
    n /= 2;
    
  • whenever you do the operation 3n + 1, you have to do the operation n / 2 as well for the next step; this is obvious.
    We can do these two operations in if statement (#28) and make cycle_length += 2
  • while ( n != 1 ) {
        if ( n % 2 == 1 ) {
            n = 3 * n + 1;
            n /= 2;
            cycle_length += 2;
        }
        else {
            n /= 2;
            cycle_length++;
        }
    }
    

Full Solution


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <algorithm>
#define long long LL

using namespace std;

int main ()
{
    int i, j;

    while ( scanf ("%d %d", &i, &j) != EOF ) {

        int temp_i = i;
        int temp_j = j;

        if ( i > j ) swap (i, j);

        int max_cycle_length = 0;
        int cycle_length;

        while ( i <= j ) {
            unsigned int n = i;
            cycle_length = 1;

            while ( n != 1 ) {
                if ( n % 2 == 1 ) n = 3 * n + 1;
                else n /= 2;
                cycle_length++;
            }

            if ( cycle_length > max_cycle_length )
                max_cycle_length = cycle_length;

            i++;
        }

        printf ("%d %d %d\n", temp_i, temp_j, max_cycle_length);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

About these ads

15 thoughts on “UVa : 100 (The 3n + 1 problem)

  1. /* @JUDGE_ID:kimda	100 C	"sample loop" */
    /* @BEGIN_OF_CODE */
    #include <stdio.h>
    void main()
    {
    	long num,n,i,j,count,max_cycle;
    	long tmp,itmp,jtmp;
    
    	while(scanf("%ld %ld",&i,&j)!=EOF)
    	{
    		if(i==0 && j==0)
    			break;
    		max_cycle=0;
    		itmp=i;
    		jtmp=j;
    		if(i>j)
    		{
    			tmp=itmp;
    			itmp=jtmp;
    			jtmp=tmp;
    		}
    		for(n=itmp;n<=jtmp;n++)
    		{ 
    			num=n;
    			count=1;
    			while(num!=1)
    			{
    				if(!(num%2))
    				{
    					num/=2;
    					count++;				
    				}
    				else
    				{
    					num=(num*3)+1;
    					count++;
    				}
    				printf("%d\n",n);
    			}
    			if(max_cycle < count)
    				max_cycle=count;
    		}
    		printf("%ld %ld %ld\n",i,j,max_cycle);
    	}
    }
    /* @END_OF_CODE */
    
  2. #include

    long int count=0;

    void f(long int n)
    {
    if(n==1)
    count++;
    else if(n%2!=0)
    {
    count++;
    f(3*n+1);
    }
    else
    {
    count++;
    f(n/2);
    }
    }

    int main()
    {
    long int a,b,max,i,atemp,btemp,temp;
    while(scanf(“%lld%lld”,&a,&b)==2)
    {
    if(a==0||b==0)
    break;
    atemp=a;
    btemp=b;
    if(a>b)
    {
    temp=atemp;
    atemp=btemp;
    btemp=temp;
    }
    max=0;
    for(i=atemp;imax)
    max=count;
    }
    printf(“%ld %ld %ld\n”,a,b,max);
    }

    return 0;
    }
    // Run time .664s

  3. #include
    #include
    #include
    #define foq(i,start,end) for(long long i=start;i<=end;i++)
    #define fo(i,start,end) for(long long i=start;i<end;i++)
    using namespace std;
    int main()
    {
    long long i,j,count;

    while((scanf("%lld%lld",&i,&j)==2))
    {
    long long max=0;
    long long d=i;
    long long b=j;
    if(j1)
    {
    if((n/2)*2==n)
    {
    n=n/2;
    count++;

    }
    else
    {
    n=3*n+1;
    count++;
    }

    }
    if(count>max)
    {
    max=count;
    }
    }
    }
    cout<<d<<" "<<b<<" "<<max<<endl;
    }

    return 0;
    }

    //Run time: .656s

  4. Solution:
    100 : 3n+1

    #include
    int main()
    {
    long int i,j,n1,n2,max=0,l,temp;
    while(scanf(“%ld %ld”,&n1,&n2)==2){
    printf(“%ld”,n1);
    printf(” %ld”,n2);
    max=0;
    if(n2<n1){
    temp=n2;
    n2=n1;
    n1=temp;
    }
    for(j=n1;jmax) max=l;
    }
    printf(” %ld\n”,max);
    }
    return 0;
    }

    for solution of this problem and other more problem visit http://uvasolve.co.cc

  5. #include
    #include
    #include

    using namespace std;

    unsigned long calc(unsigned long n);

    int main()
    {
    int i, j, a, b, m;
    vector temp;

    while while (cin >> i >> j)
    {

    if (i < j)
    {
    a = i;
    b = j;
    }

    else
    {
    a = j;
    b = i;
    }

    temp.clear();
    for (unsigned int k = a; k <= b; ++k)
    {
    temp.push_back(calc(k));
    }

    m = *max_element(temp.begin(), temp.end());

    cout << i << ' ' << j << ' ' << m << endl;
    }
    }

    unsigned long calc(unsigned long n)
    {
    unsigned long ret = 1;
    while (n != 1)
    {
    if (n % 2 == 0)
    n = n/2;
    else
    n = 3*n + 1;
    ret++;
    }

    return ret;
    }

  6. #include
    #include
    #include

    using namespace std ;

    int loopTest(int x)
    {
    int count = 0;
    if(x == 1)
    {
    count++;
    return count;
    }
    else
    {
    count++;
    while(x > 1)
    {
    if(x%2 == 0)
    {
    x = x/2;
    count++;
    }
    else
    {
    x = 3*x+1;
    count++;
    }
    }
    }
    return count;
    }

    int main()
    {
    int a, b;

    while(cin >>a>>b)
    {
    if((a & b) != EOF)
    {

    int temp = 0;
    int a1 = a ;
    int b1 = b ;
    if(a > b)
    {
    int temporary = a ;
    a = b ;
    b = temporary ;
    }

    while(a temp)
    temp = counter;
    a++;

    }
    cout <<a1<<" "<< b1<<" "<<temp<<endl;

    }
    }

    return 0;
    }

  7. #include
    #include
    #include
    using namespace std;

    int algo(int start, int end) {
    int max = 0;
    int count;
    int i;
    if(start > end) {
    i = start;
    start = end;
    end = i;
    }
    for (int temp = start; temp max)
    max = count;
    }
    return max;
    }

    int main() {
    int i , j;
    while (scanf(“%d %d”, &i, &j) != EOF) {
    cout << i << " " << j << " " << algo(i, j) << endl;
    }
    return 0;
    }

  8. As Kumar said above, the data type should be changed to long long int. Before I added the memoization this solution took 0.702 seconds on programming-challenges.com, after I added it the runtime went down to 0.072 seconds, 10x decrease!

    #include “stdafx.h”
    #include

    //hangs if an input num is >= 113383
    //rt 0.072 s
    //with out memoization took 0.702 s

    int seqLen(int inNum)
    {
    int curCount = 1;
    while (inNum != 1)
    {
    ++curCount;
    if (inNum % 2 == 0)
    {
    inNum /= 2;
    }
    else
    {
    inNum *= 3;
    ++inNum;
    }
    }
    return curCount;
    }

    int main()
    {
    const int maxSize = 1000000;
    int numOne;
    int numTwo;
    int *results = new int[maxSize];
    for (int i = 0; i < maxSize; i++)
    {
    results[i] = 0;
    }
    while (scanf("%d%d", &numOne, &numTwo) != EOF)
    {
    int startNum = (numOne numTwo) ? numOne : numTwo;
    int maxCount = -1;
    for (int i = startNum; i maxCount)
    maxCount = curCount;
    }
    printf(“%d %d %d\n”, numOne, numTwo, maxCount);
    }
    return 0;
    }

  9. #include
    #include
    #include
    using namespace std;

    size_t get_steps(size_t n)
    {
    size_t original = n;
    size_t steps = 1;
    while (n != 1) {
    if (n % 2 == 0) n /= 2;
    else n = n*3 + 1;
    ++steps;
    }
    return steps;
    }

    int main()
    {
    size_t i, j, temp, max, t_i, t_j;
    while (scanf(“%lu%lu”, &i, &j) != EOF) {
    t_i = i; t_j = j;
    if (i > j) swap(i, j);
    max = temp = 0;
    for (size_t k = i; k max) max = temp;
    }
    cout << t_i << " " << t_j << " " << max << endl;
    }
    return 0;
    }

  10. I like the helpful info you supply on your

    articles. I’ll bookmark your blog and check once more right here

    regularly. I’m relatively certain

    I’ll be told lots of new stuff proper right

    here! Good luck for the following!

  11. import java.util.Scanner;
    import java.util.Random;
    import java.math.BigInteger;

    public class horse { // save as Main.java
    public static void main(String[] args)
    {Scanner in = new Scanner(System.in);
    while( in!=null){

    int i=in.nextInt();
    int j=in.nextInt();
    int count=1,max=0,c=0;
    int tmpi=i,tmpj=j;
    if(j=i)
    { c=i;
    while(c!=1)
    {
    count++;
    if(c%2==0)
    c/=2;
    else
    c=3*c+1;

    }
    if(count>max)
    max=count;
    count=1;
    i++;
    }
    System.out.println(tmpi+” “+tmpj+” “+max);
    }
    }

    }

    Runtime error?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s