/home/toolbox/public_html/solutions/6/674/d.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 * See Competitive Programmer's Handbook Chapter 7
32 */
33
34 #define MAX_COINS 7500
35 #define COIN_STOP 7490
36 #define BIG_NUMBER 0x7FFFFFFF
37
38 long long int count[MAX_COINS];
39 long long int coins[5] = { 1, 5, 10, 25, 50 };
40 long long int chg;
41
42
43 long long int returnCount(long long int num)
44 {
45 /* FUNCTION returnCount */
46 long long int toReturn;
47
48 if (0 > num)
49 {
50 /* invalid case -- no contribution */
51 toReturn = 0;
52 } /* invalid case -- no contribution */
53 else
54 {
55 /* return cached value */
56 toReturn = count[num];
57 } /* return cached value */
58 return toReturn;
59 } /* FUNCTION returnCount */
60
61 long long int countCoins(long long int num)
62 {
63 /* FUNCTION countCoins */
64 long long int toReturn;
65 long long int i;
66
67 toReturn = 0;
68 for (i=1; 5>i; i++)
69 {
70 /* for each coin */
71 toReturn = toReturn + returnCount(num - coins[i]);
72 } /* for each coin */
73 return toReturn;
74 } /* FUNCTION countCoins */
75
76 void init()
77 {
78 /* FUNCTION init */
79 long long int i;
80
81 count[0] = 1;
82 count[1] = 1;
83
84 for (i=2; COIN_STOP>i; i++)
85 {
86 /* for each coin value */
87 count[i] = countCoins(i);
88 printf("%lld: %lld\n", i, count[i]);
89 } /* for each coin value */
90 } /* FUNCTION init */
91
92 void dump()
93 {
94 /* FUNCTION dump */
95 } /* FUNCTION dump */
96
97 int getInput()
98 {
99 /* FUNCTION getInput */
100 int dataReadFlag;
101
102 dataReadFlag = 1 == scanf(" %lld ", &chg);
103 return (dataReadFlag);
104 } /* FUNCTION getInput */
105
106
107 void process()
108 {
109 /* FUNCTION process */
110 printf("%lld\n", count[chg]);
111 } /* FUNCTION process */
112
113 int main()
114 {
115 /* main */
116 int moreToDo;
117
118 init();
119 moreToDo = getInput();
120 while (moreToDo)
121 {
122 /* while */
123 process();
124 moreToDo = getInput();
125 } /* while */
126
127 return EXIT_SUCCESS;
128 } /* main */
129