20111215

ACM 357 Let Me Count The Ways

ACM674
要用long long,要不然會爆掉。

/* ACM 357 Let Me Count The Ways
 * mythnc
 * 2011/12/15 11:15:23   
 * run time: 0.044
 */
#include <stdio.h>

#define MAXN 30001
#define COIN 5

void cal(long long *);

int main(void)
{
    int n;
    long long ans[MAXN] = { 0 };

    cal(ans);

    while (scanf("%d", &n) == 1)
        if (ans[n] == 1)
            printf("There is only 1 way to produce %d cents change.\n", n);
        else
            printf("There are %lld ways to produce %d cents change.\n", ans[n], n);

    return 0;
}

/* cal: pre calulate the answer */
void cal(long long *ans)
{
    int money[COIN] = {1, 5, 10, 25, 50};
    int i, j;

    ans[0] = 1;
    for (i = 0; i < COIN; i++)
        for (j = money[i]; j < MAXN; j++)
            ans[j] += ans[j - money[i]];
}

沒有留言: