UVa 357

Its basically a variation of the famous "Coin Change" problem. The code is pretty much self-explanatory. Here it is:

#include<stdio.h>
unsigned long tab[6][30001];
int denom[]={0,1,5,10,25,50};
int main()
{
    // tab[denom][val]
    // tab[i][j] = no of ways we can pay value j using upto ith denominations
    for(int i=0;i<6;++i)
    {
        tab[i][0]=1;
    }
    for(int i=0; i<30001;++i )
    {
        tab[0][i]=0;
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(tab[5][n]!=0)
        {
            if(tab[5][n]==1) printf("There is only 1 way to produce %d cents change.\n",n);
            else printf("There are %lu ways to produce %d cents change.\n",tab[5][n],n);
            continue;
        }
        bool found =false;
        for(int i=1;i<=n;++i)
        {
            if(found) break;
            for(int j=1;j<=5;++j)
            {
                if(!tab[j][i])
                {
                    if(denom[j]>i) tab[j][i]=tab[j-1][i];
                    else
                    {
                        tab[j][i]=tab[j-1][i]+tab[j][i-denom[j]];
                    }
                }
                if(j==5 && i==n)
                {
                    if(tab[5][n]==1) printf("There is only 1 way to produce %d cents change.\n",n);
                    else printf("There are %lu ways to produce %d cents change.\n",tab[5][n],n);
                    found =true;

                }
            }
        }

    }
    return 0;
}