Tuesday, October 11, 2011

[UVa] 100 - 3n + 1

I'm currently trying to optimize this code as much as I can. If you have some suggestions please do mail me or post a comment at lest.
Method [On the fly calculation + Memoization]
1. Take input and swap if needed.
2. Then on a loop from the low to the high, call the calculation function for each iteration.
3. In the calculation function, if for some number the value is already available, return right from there. This is done even in the middle of the divide and multiplication iterations.
4. For additional optimizing, I use >> in place of divide by 2.

#include <stdio.h>
#define isEven(j) (!(j & 0x01))
#define SWAP(a,b) {if (b<a) {int t=a; a=b; b=t;}}
int dp[1000000];
int get(int i)
{
    int n, counter;

    counter=1;
    n = i;
    while (n>1)
    {

        if (n<1000000 && dp[n])
        {
            return dp[i]=(counter+=(dp[n]-1));
        }
        counter++;
        if ( isEven(n) )
        {
            n = n >> 1;
        } else
        {
            n = (n*3 + 1) >> 1;
            counter++;
        }
    }
    dp[i]=counter;
    return counter;
}
int pro()
{
    int i, n, counter;
    for (i=1 ; i<=1000000 ; i++)
    {
        counter=1;
        n = i;
        while (n>1)
        {

            if (n<i)
            {
                counter+=(dp[n]-1);
                break;
            }
            counter++;
            if ( isEven(n) )
            {
                n = n >> 1;
            } else
            {
                n = (n*3 + 1) >> 1;
                counter++;
            }
        }
        dp[i]=counter;
    }
    return 0;
}

int main()
{
    int i, a, b, low, high;
    int max;
    while (scanf("%d %d",&a,&b)==2)
    {
        low = a; high=b;
        SWAP(low,high);
        max=-1;
        for (i=low ; i<=high ; i++)
        {
            if (get(i)>max)
                max = dp[i];
        }
        printf("%d %d %d\n",a,b,max);
    }
    return 0;
}

No comments:

Post a Comment

Post your comment here. If you want to say something about programming problems, scripts, software etc, please try to be as descriptive as possible.

Connect Rapoo MT750S with Linux (Tested on Manjaro)

 I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...