/home/toolbox/public_html/solutions/6/674/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 2015-03-11
19 * Purpose: Fun
20 * Problem: 674
21 */
22
23 /*
24 * This template reads lines of data at a time until end of file.
25 */
26
27 /* Dynamic Programming
28 * count is the cache (memomization)
29 * countCoins is the recursive solution
30 */
31
32 #define MAX_COINS 7500
33 #define COIN_STOP 7490
34 #define COIN_TYPES 5
35 #define INT int
36
37 INT count[MAX_COINS];
38 INT coins[COIN_TYPES] = { 50, 25, 10, 5, 1 };
39 INT chg;
40
41
42 void init()
43 {
44 /* FUNCTION init */
45 INT i;
46 INT j;
47
48 count[0] = 1;
49 for (i=1; COIN_STOP>i; i=i+1)
50 {
51 /* for each coin value */
52 count[i] = 0;
53 } /* for each coin value */
54
55 for (j=0; COIN_TYPES>j; j++)
56 {
57 /* for each coin type */
58 for (i=0; COIN_STOP>i; i++)
59 {
60 /* for each possible query */
61 if (i >= coins[j])
62 {
63 /* could be some of this coin */
64 count[i] = count[i] + count[i-coins[j]];
65 } /* could be some of this coin */
66 } /* for each possible query */
67 } /* for each coin type*/
68 } /* FUNCTION init */
69
70 void dump()
71 {
72 /* FUNCTION dump */
73 } /* FUNCTION dump */
74
75 int getInput()
76 {
77 /* FUNCTION getInput */
78 int dataReadFlag;
79
80 dataReadFlag = 1 == scanf(" %d ", &chg);
81 return (dataReadFlag);
82 } /* FUNCTION getInput */
83
84
85 void process()
86 {
87 /* FUNCTION process */
88 printf("%d\n", count[chg]);
89 } /* FUNCTION process */
90
91 int main()
92 {
93 /* main */
94 int moreToDo;
95
96 init();
97 moreToDo = getInput();
98 while (moreToDo)
99 {
100 /* while */
101 process();
102 moreToDo = getInput();
103 } /* while */
104
105 return EXIT_SUCCESS;
106 } /* main */
107