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;

}