/home/toolbox/public_html/solutions/6/674/c.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:
20 * Problem: 674
21 */
22
23 /*
24 * This template reads lines of data at a time until end of file.
25 */
26
27 #define C50 50
28 #define C25 25
29 #define C10 10
30 #define C5 5
31 #define I50 4
32 #define I25 3
33 #define I10 2
34 #define I5 1
35 #define I1 0
36
37 int chg;
38 int strt[5];
39
40 void init()
41 {
42 /* FUNCTION init */
43 /*
44 50 25 10 5 1
45 1(1) 0 0 0 0 0
46
47 50 25 10 5 1
48 5(2) 0 0 0 1 0
49 0 0 0 0 5
50
51 50 25 10 5 1
52 10(4) 0 0 1 0 0
53 0 0 0 2 0
54 0 0 0 1 5
55 0 0 0 0 10
56
57 50 25 10 5 1
58 25(13) 0 1 0 0 0
59 0 0 2 1 0
60 0 0 2 0 5
61 0 0 1 3 0
62 0 0 1 2 5
63 0 0 1 1 10
64 0 0 1 0 15
65 0 0 0 5 0
66 0 0 0 4 5
67 0 0 0 3 10
68 0 0 0 2 15
69 0 0 0 1 20
70 0 0 0 0 25
71
72 50 25 10 5 1
73 50(50) 1 0 0 0 0
74 0 2 0 0 0
75 0 1 2 1 0
76 0 1 2 0 5
77 0 1 1 3 0
78 0 1 1 2 5
79 0 1 1 1 10
80 0 1 1 0 15
81 0 1 0 5 0
82 0 1 0 4 5
83 0 1 0 3 10
84 0 1 0 2 15
85 0 1 0 1 20
86 0 1 0 0 25
87 0 0 5 0 0
88 0 0 4 2 0
89 0 0 4 1 5
90 0 0 4 0 10
91 0 0 3 4 0
92 0 0 3 3 5
93 0 0 3 2 10
94 0 0 3 1 15
95 0 0 3 0 20
96 0 0 2 6 0
97 0 0 2 5 5
98 0 0 2 4 10
99 0 0 2 3 15
100 0 0 2 2 20
101 0 0 2 1 25
102 0 0 2 0 30
103 0 0 1 8 0
104 0 0 1 7 5
105 0 0 1 6 10
106 0 0 1 5 15
107 0 0 1 4 20
108 0 0 1 3 25
109 0 0 1 2 30
110 0 0 1 1 35
111 0 0 1 0 40
112 0 0 0 10 0
113 0 0 0 9 5
114 0 0 0 8 10
115 0 0 0 7 15
116 0 0 0 6 20
117 0 0 0 5 25
118 0 0 0 4 30
119 0 0 0 3 35
120 0 0 0 2 40
121 0 0 0 1 45
122 0 0 0 0 50
123
124 */
125 } /* FUNCTION init */
126
127 void dump(int t[5])
128 {
129 /* FUNCTION dump */
130 printf("%d %d %d %d %d\n", t[4], t[3], t[2], t[1], t[0]);
131 } /* FUNCTION dump */
132
133 int getInput()
134 {
135 /* FUNCTION getInput */
136 int dataReadFlag;
137
138 dataReadFlag = 1 == scanf(" %d ", &chg);
139 return (dataReadFlag);
140 } /* FUNCTION getInput */
141
142 int doit5(int coins[5])
143 {
144 /* FUNCTION doit5 */
145 int i;
146 int counter;
147
148 if (0 == strt[I5])
149 {
150 /* no nickels */
151 /* if a penny is present -- this counts */
152 if (0 < strt[I1])
153 {
154 counter = 1;
155 }
156 else
157 {
158 counter = 0;
159 }
160 } /* no nickels */
161 else
162 {
163 counter = strt[I5] + 1;
164 }
165 return counter;
166 } /* FUNCTION doit5 */
167
168 int doit10(int coins[5])
169 {
170 /* FUNCTION doit10 */
171 int i;
172 int counter = 0;
173
174 if (0 < coins[I10])
175 {
176 counter = 2;
177 }
178 counter = doit5(coins);
179 for (i=coins[I10]-1; 0<=i; i--)
180 {
181 /* for each dime piece */
182 coins[I10] = i;
183 coins[I5] = coins[I5] + 2;
184 counter = counter + doit5(coins);
185 } /* for each dime piece */
186 return counter;
187 } /* FUNCTION doit10 */
188
189 int doit25(int coins[5])
190 {
191 /* FUNCTION doit25 */
192 int i;
193 int counter = 0;
194
195 counter = doit10(coins);
196 for (i=coins[I25]-1; 0<=i; i--)
197 {
198 /* for each quarter piece */
199 coins[I25] = i;
200 coins[I10] = coins[I10] + 2;
201 coins[I5] = coins[I5] + 1;
202 counter = counter + doit10(coins);
203 } /* for each quarter piece */
204 return counter;
205 } /* FUNCTION doit25 */
206
207 int doit50(int coins[5])
208 {
209 /* FUNCTION doit50 */
210 int i;
211 int counter = 0;
212
213 counter = doit25(coins);
214 for (i=coins[I50]-1; 0<=i; i--)
215 {
216 /* for each 50 cent piece */
217 coins[I50] = i;
218 coins[I25] = coins[I25] + 2;
219 counter = counter + doit25(coins);
220 } /* for each 50 cent piece */
221 return counter;
222 } /* FUNCTION doit50 */
223
224 int countCoins(int chg)
225 {
226 /* FUNCTION countCoins */
227 int tmp;
228 int t;
229
230 tmp = chg;
231 t = tmp / C50;
232 tmp = tmp - (t * C50);
233 strt[I50] = t;
234 t = tmp / C25;
235 tmp = tmp - (t * C25);
236 strt[I25] = t;
237 t = tmp / C10;
238 tmp = tmp - (t * C10);
239 strt[I10] = t;
240 t = tmp / C5;
241 tmp = tmp - (t * C5);
242 strt[I5] = t;
243 strt[I1] = tmp;
244
245 DEBUG printf("%d: ", chg);
246 DEBUG dump(strt);
247 tmp = doit50(strt);
248 return tmp;
249
250 } /* FUNCTION countCoins */
251
252 void process()
253 {
254 /* FUNCTION process */
255 int cnt;
256
257 printf("%d: ", chg);
258 if (0 == chg)
259 {
260 cnt = 1;
261 }
262 else
263 {
264 /* make a change */
265 cnt = countCoins(chg);
266 } /* make a change */
267 printf("%d\n", cnt);
268 } /* FUNCTION process */
269
270 int main()
271 {
272 /* main */
273 int moreToDo;
274
275 init();
276 moreToDo = getInput();
277 while (moreToDo)
278 {
279 /* while */
280 process();
281 moreToDo = getInput();
282 } /* while */
283
284 return EXIT_SUCCESS;
285 } /* main */
286