/home/toolbox/public_html/solutions/101/10142/f.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 <stdlib.h>
7 #include <math.h>
8 #include <stdint.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 #define MAXINT 2147483647
16 #define LINESIZE 256
17 #define MAX_CANDIDATES 22
18 #define MAX_BALLOTS 1002
19
20 /* fprintf(stderr, "functionName: message", varslist); */
21
22 /*
23 * Author:
24 * Date:
25 * Purpose:
26 * Problem:
27 */
28
29 /*
30 * This template reads data a specified number of times.
31 */
32
33 int numberOfTimes;
34 int numCandidates;
35 char candidates[MAX_CANDIDATES][LINESIZE];
36 int numBallots;
37 int ballots[MAX_BALLOTS][MAX_CANDIDATES]; /* table of all ballots cast by all voters */
38 char line[LINESIZE];
39 int elect[MAX_CANDIDATES]; /* current vote total */
40 int minWin;
41 int maxFound;
42 int minFound;
43 int winner;
44 int stillInRace[MAX_CANDIDATES];
45
46 void init()
47 {
48 /* FUNCTION init */
49 scanf("%d ", &numberOfTimes);
50 } /* FUNCTION init */
51
52 void dump()
53 {
54 /* FUNCTION dump */
55 int i;
56 int v;
57
58 printf("dump\n");
59 printf("Number of Candidates: %d\n", numCandidates);
60 for (i=1; i<=numCandidates; i++)
61 {
62 /* for */
63 printf("%d:[%s] %d\n", i, candidates[i], elect[i]);
64 } /* for */
65 printf("Number of Votes: %d\n", numBallots);
66 printf("minFound = %d\n", minFound);
67 printf("maxFound = %d\n", maxFound);
68 for (v=1; v<=numBallots; v++)
69 {
70 /* for */
71 for (i=1; i<=numCandidates; i++)
72 {
73 /* for */
74 printf("%d ",ballots[v][i]);
75 } /* for */
76 printf("\n");
77 } /* for */
78
79 } /* FUNCTION dump */
80
81 int getline()
82 {
83 /* FUNCTION getline */
84 int i;
85 int ret = FALSE;
86
87 if ( fgets(line, 255, stdin) )
88 {
89 /* if */
90 i = strchr(line, '\n') - line;
91 if ((0>i) || (255<i))
92 {
93 i=0;
94 }
95 line[i] = '\0';
96 ret = (0 < strlen(line));
97 } /* if */
98
99 return ret;
100 } /* FUNCTION getline */
101
102 void getInput()
103 {
104 /* FUNCTION getInput */
105 int i;
106 int v;
107 int more;
108
109 /* how many candidates */
110 scanf("%d ",&numCandidates);
111 /* grab all of the candidates */
112 for (i=1; i<=numCandidates; i++)
113 {
114 /* for */
115 scanf("%[^\n] ",candidates[i]);
116 } /* for */
117 /* grab all of the ballots */
118 more = getline();
119 v = 1;
120 while (more)
121 {
122 /* while */
123 sscanf(line, "%d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d",
124 &ballots[v][1], &ballots[v][2], &ballots[v][3], &ballots[v][4], &ballots[v][5],
125 &ballots[v][6], &ballots[v][7], &ballots[v][8], &ballots[v][9], &ballots[v][10],
126 &ballots[v][11], &ballots[v][12], &ballots[v][13], &ballots[v][14], &ballots[v][15],
127 &ballots[v][16], &ballots[v][17], &ballots[v][18], &ballots[v][19], &ballots[v][20]);
128 v++;
129 more=getline();
130 } /* while */
131 numBallots = v - 1;
132 } /* FUNCTION getInput */
133
134 void tally()
135 {
136 /* FUNCTION tally */
137 /* tally up current votes into elect */
138 int i;
139
140 for (i=1; i<=numCandidates; i++)
141 {
142 /* for */
143 elect[i] = 0;
144 } /* for */
145
146 for (i=1; i<=numBallots; i++)
147 {
148 /* for */
149 elect[ballots[i][1]]++;
150 } /* for */
151 } /* FUNCTION tally */
152
153
154 int checkWin()
155 {
156 /* FUCNTION checkWin */
157 int i;
158
159 winner = -1;
160 for (i=1; (i<=numCandidates) && (-1 == winner); i++)
161 {
162 /* for */
163 if (minWin <= elect[i])
164 {
165 /* winner found */
166 winner = i;
167 } /* winner found */
168 } /* for */
169 return (-1 != winner);
170 } /* FUNCTION checkWin */
171
172 int checkTie()
173 {
174 /* FUCNTION checkTie */
175 int i;
176
177 maxFound = -1;
178 minFound = MAXINT;
179 for (i=1; (i<=numCandidates); i++)
180 {
181 /* for */
182 DEBUG printf("i=%d elect[%d]=%d minFound=%d maxFound=%d\n", i, i, elect[i], minFound, maxFound);
183 if (0 != stillInRace[i])
184 {
185 /* candidate can be looked for */
186 if (elect[i] > maxFound)
187 {
188 /* if */
189 maxFound = elect[i];
190 } /* if */
191 if (elect[i] < minFound)
192 {
193 /* if */
194 minFound = elect[i];
195 } /* if */
196 } /* candidate can be looked for */
197 } /* for */
198 DEBUG printf("i=%d elect[%d]=%d minFound=%d maxFound=%d\n", i, i, elect[i], minFound, maxFound);
199 return (minFound == maxFound);
200 } /* FUNCTION checkTie */
201
202 void cleanse(int ballotToProcess, int location)
203 {
204 /* FUNCTION cleanse */
205 int i;
206
207 DEBUG printf("cleanse: ballotToProcess=%d location=%d\n", ballotToProcess, location);
208 i = location;
209 if (i == numCandidates)
210 {
211 /* eliminate last guy */
212 ballots[ballotToProcess][i] = ballots[ballotToProcess][i-1];
213 } /* eliminate last guy */
214 else
215 {
216 /* promote votes */
217 while (i < numCandidates)
218 {
219 /* while */
220 ballots[ballotToProcess][i] = ballots[ballotToProcess][i+1];
221 i++;
222 } /* while */
223 } /* promote votes */
224
225 } /* FUNCTION cleanse */
226
227 void eliminate()
228 {
229 /* FUNCTION eliminate */
230 int i;
231 int j;
232
233 for (i=1; i<=numBallots; i++)
234 {
235 /* for -- inspect each ballot */
236 for (j=1; j<=numCandidates; j++)
237 {
238 /* for each vote cast */
239 DEBUG printf("minFound=%d i=%d j=%d ballots[%d][%d]=%d elect=%d\n", minFound, i, j, i, j, ballots[i][j], elect[ballots[i][j]]);
240 if (minFound == elect[ballots[i][j]])
241 {
242 /* get rid of this guy */
243 stillInRace[ballots[i][j]] = 0;
244 cleanse(i, j);
245 } /* get rid of this guy */
246 } /* for each vote cast */
247 } /* for -- inspect each ballot */
248 } /* FUNCTION eliminate */
249
250
251 void process()
252 {
253 /* FUNCTION process */
254 int i;
255
256 for (i=1; i<= numCandidates; i++)
257 {
258 /* enable all candidates */
259 stillInRace[i] = 1;
260 } /* enable all candidates */
261 minWin = (numBallots / 2) + 1;
262 tally();
263 DEBUG dump();
264 while ((! checkWin()) && (! checkTie()))
265 {
266 /* while */
267 DEBUG printf("in loop when no tie or win\n");
268 eliminate();
269 DEBUG printf("returned from eliminate\n");
270 DEBUG dump();
271 DEBUG printf("calling tally\n");
272 tally();
273 } /* while */
274
275 if (-1 != winner)
276 {
277 /* winner */
278 printf("%s\n\n", candidates[winner]);
279 } /* winner */
280 else
281 {
282 /* tie */
283 for (i=1; i<numCandidates; i++)
284 {
285 /* for */
286 if (maxFound == elect[i])
287 {
288 /* print tie-er */
289 printf("%s\n", candidates[i]);
290 } /* print tie-er */
291 } /* for */
292 printf("\n");
293 } /* tie */
294
295 } /* FUNCTION process */
296
297 int main ()
298 {
299 /* main */
300 int i;
301
302 init();
303 for (i=1; i<=numberOfTimes; i++)
304 {
305 /* while */
306 getInput();
307 process();
308 } /* while */
309
310 return EXIT_SUCCESS;
311 } /* main */
312