1. C, Andreas Kunft



/*

 * ACM Programming Contest

 * Problem: /*

 * ACM Programming Contest

 * Problem: 357 (Let me count the ways)

 * Status: Accepted

 * Language: ANSI C

 * Runtime: 0.008

 * Date: 2009-05-27 12:56:39

 * Author: Andreas Kunft

 */



#include <stdio.h>

#include <string.h>



#define MAXTOTAL 30001

#define COINS 5



long long nway[MAXTOTAL];



int coin[COINS] = { 50,25,10,5,1 };



int main() {

    int i, j, n, c;

    nway[0] = 1;

    for (i=0; i< COINS; i++) {

        c = coin[i];

        for (j=c; j< MAXTOTAL; j++)

            nway[j] += nway[j-c];

    }



    while (scanf("%d",&n) == 1) {

        if (nway[n] > 1)

            printf("There are %lld ways to produce %d cents change.\n", nway[n], n);

        else

            printf("There is only 1 way to produce %d cents change.\n", n);

    }

    return 0;

}