UVA 116 Solution CPP code

Create two arrays in addition to the input array. One is the DP array, and one is the path array. dp[i][j] = in[i][j] + min(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]). Make sure that you wrap around the top and bottom of the matrix (use modulo, or just an if statement).

For the path, you must keep an array of strings (or whatever you like) to hold the current path to that point. Prefer lexicographically shorter paths when two DP cells have the same value. Note that lexicographically shorter in this problem means that you minimize the row number, and not the ASCII value of the string. For example:

1 10 10 10
1 2 3 4

In ASCII terms, and normal string comparison terms, the first string is lexicographically earlier. But in this problem, they want the latter.

Remember it does not matter you from left to right or right to left.

CODE:

#include<stdio.h>


#define MIN(a,b) a<b? a:b
#define maxe 1<<30

int p[11][101],r,c;



int main(){


    int i,j,rp;
    long long a[11][101],tmp,min,f;

 while(scanf("%d %d",&r,&c)!=EOF){

     for(i=0;i<r;i++)
     for(j=0;j<c;j++)
     scanf("%lld",&a[i][j]);

    for(j=c-2;j>=0;j--)
    for(i=0;i<r;i++){

        tmp=a[i][j];

        rp=i-1;
        if(rp<0)rp=r-1;
        a[i][j]=tmp+a[rp][j+1];
        p[i][j]=rp;



        rp=i;f=1;
        if(a[i][j]>tmp+a[rp][j+1]||(a[i][j]==tmp+a[rp][j+1]&&i==0)){
        a[i][j]=tmp+a[rp][j+1];
        p[i][j]=rp;
        f=0;
        }


        rp=i+1;
        if(rp==r)rp=0;
        if(a[i][j]>tmp+a[rp][j+1]||(a[i][j]==tmp+a[rp][j+1]&&i==0&&f)||(a[i][j]==tmp+a[rp][j+1]&&i==r-1)){
        a[i][j]=tmp+a[rp][j+1];
        p[i][j]=rp;
        }



        }

     min=maxe;
     for(i=0;i<r;i++){
        if(min>a[i][0]){
        min=a[i][0];
        rp=i;
        }
     }

    for(j=0;j<c;j++){

        printf("%d",rp+1);
        if(j<c-1)printf(" ");
        rp=p[rp][j];
        }

    printf("\n%lld\n",min);


     }

}

UVA 701 Exclusive solution

<script type="text/javascript"> ch_fluidH = 1; ch_nump = "4"; ch_client = "faltu"; ch_width = 550; ch_height = "auto"; ch_type = "mpu"; ch_sid = "Chitika Default"; ch_color_site_link = "0000CC"; ch_color_title = "0000CC"; ch_color_border = "FFFFFF"; ch_color_text = "000000"; ch_color_bg = "FFFFFF"; </script> <script src="http://scripts.chitika.net/eminimalls/amm.js" type="text/javascript"> </script> Let P denotes the prefix, T denotes the # of lost digits. We are searching for N, that the prefix of 2^N is P.
We have an inequlity of
P*10^T <= 2^N < (P+1)*10^T
thus log2(P*10^T) <= log2(2^N) < log2((P+1)*10^T),
which is log2(P)+T*log2(10) <= N < log2(P+1)+T*log2(10).
Also, we know that P < 10^(T-1),
that is T > log10(P)+1.
Then, we can brute force on T and find the minmum N.

#include<iostream>
#include<stdio.h>
#include<math.h>

using namespace std;



long double ab(long double prf ){
    long double lo,up,f,t;
    lo=log2l(prf);
    up=log2l(prf+1);
    f=log2l(10);
    t=ceill(log10l(prf+0.5))+1;
    for (; ceill(lo+t*f) != floorl(up+t*f); t += 1) {}
    return ceill(lo+t*f);

}



int main(){

    long double prf;
    while(cin>>prf){

        printf("%lld\n",(long long)ab(prf));
        }

    return 0;
    } 

LightOJ 10047 solution & CPP code

Its a dp problem.
Keep on counting minimum possible cost for each position. Use previous value to avoid calculating same thing again and again.

#include<stdio.h>
#define MIN(a,b) a<b? a:b
#define inf 99999999


int main()
{

    int fc,cost[22][5],a[22][5],i,j,n,t,kase,x,y;
    scanf("%d",&t);
    kase=0;
    while (kase++<t)
    {

        scanf("%d",&n);


        for (i=1;i<=n;i++)
            for (j=1;j<=3;j++)
                scanf("%d",&a[i][j]);


        cost[1][1]=a[1][1];
        cost[1][2]=a[1][2];
        cost[1][3]=a[1][3];

        for (i=2;i<=n;i++)
            {
                cost[i][1]=cost[i-1][2]+a[i][1];
                cost[i][1]=MIN(cost[i][1],cost[i-1][3]+a[i][1]);

                cost[i][2]=cost[i-1][1]+a[i][2];
                cost[i][2]=MIN(cost[i][2],cost[i-1][3]+a[i][2]);

                cost[i][3]=cost[i-1][2]+a[i][3];
                cost[i][3]=MIN(cost[i][3],cost[i-1][1]+a[i][3]);

            }
        fc=inf;
        for (i=1;i<=3;i++)
            fc=MIN(fc,cost[n][i]);

        printf("Case %d: %d\n",kase,fc);

    }

    return 0;
}

UVA 10446 solution & C++ code

ALGORITHM:

This is an DP problem.

Rather than calculating the value for a particular n and back u store it and when needed dont recalculte.

#include<stdio.h>

unsigned long long dp[70][70];

int ini()
{

    for (int i=0;i<70;i++)
        for (int j=0;j<70;j++)
            dp[i][j]=-1;

    return 0;
}

unsigned long long trib(int n,int back)
{


    if(n<=1)return 1;

    if (dp[n][back]!=-1)return dp[n][back];

    dp[n][back]=1;

    for (int i=1;i<=back;i++)
    {

        dp[n][back]+=trib(n-i,back);
    }
    return dp[n][back];

}


int main(void)

{
    int n,back,kase=1;;


    while (1)
    {

        scanf("%d%d",&n,&back);

        if (n>60)break;

        ini();

        printf("Case %d: %llu\n", kase++,trib(n,back));
    }
    return 0;

}