Advertisement
Guest User

Untitled

a guest
Nov 13th, 2010
297
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <unistd.h>
  4.  
  5. #define CLEAR(x,v) (memset((x), (v), sizeof((x))))
  6.  
  7. using namespace std;
  8.  
  9.  
  10. void
  11. solve(int prefs[][20], int v, int n, char names[][81])
  12. {
  13.     int i, j, k, run[n], indices[v], scores[n];
  14.     char foo[256];
  15.  
  16.     CLEAR(run, 1);
  17.     CLEAR(indices, 0);
  18.     CLEAR(scores, -1);
  19.  
  20.     /* count preferences */
  21.     for (i = 0; i < v; i++) {
  22.         scores[prefs[i][indices[i]] - 1]++;
  23.     }
  24.  
  25.     while (1) {
  26.         int min = n, max = 0;
  27.  
  28.         /* min max */
  29.         for (k = 0; k < n; k++) {
  30.             if (scores[k] > max)
  31.                 max = scores[k];
  32.             if (scores[k] > -1 && scores[k] < min)
  33.                 min = scores[k];
  34.         }
  35.         /*
  36.         fprintf(stdout, "\n");
  37.         fprintf(stdout, "%d %d\n", min, max);
  38.  
  39.         for (i = 0; i < v; i++) {
  40.             for (j = indices[i]; j < n; j++) {
  41.                 fprintf(stdout, "%d ", prefs[i][j]);
  42.             }
  43.             fprintf(stdout, "\n");
  44.         }
  45.         fprintf(stdout, "\n");
  46.         sleep(1);
  47.         */
  48.  
  49.         /*
  50.          * max == min: all the remaining candindates tied.
  51.          * max / n > 50: there is only one winner.
  52.          */
  53.         if (max == min || (100 * max / v > 50) ) {
  54.             for (i = 0; i < n; i++) {
  55.                 if (scores[i] == max)
  56.                     fprintf(stdout, "%s", names[i]);
  57.             }
  58.             return;
  59.         }
  60.  
  61.         /* unmark all the eliminated candidates */
  62.         for (i = 0; i < n; i++) {
  63.             if (scores[i] == min) {
  64.                 scores[i] = -1;
  65.                 run[i] = 0;
  66.             }
  67.         }
  68.  
  69.         /* redistribute votes */
  70.         for (i = 0; i < v; i++) {
  71.             if (run[prefs[i][indices[i]] - 1] == 0) {
  72.                 while (run[prefs[i][indices[i]] - 1] == 0) {
  73.                     indices[i]++;
  74.                 }
  75.                 scores[prefs[i][indices[i]] - 1]++;
  76.             }
  77.         }
  78.     }
  79. }
  80.  
  81. int
  82. main(int argc, char *argv[])
  83. {
  84.     int cases, i, j, n, v;
  85.     char *p;
  86.     char names[20][81], buff[256];
  87.     int prefs[1000][20];
  88.  
  89.     fscanf(stdin, "%d", &cases);
  90.     fgets(buff, 256, stdin); /* skip empty line */
  91.     while (cases--) {
  92.         fscanf(stdin, "%d\n", &n);
  93.         /* fprintf(stdout, "%d\n", n); */
  94.         for (i = 0; i < n; i++) {
  95.             fgets(names[i], 81, stdin);
  96.             /* fprintf(stdout, "%s", names[i]); */
  97.         }
  98.         i = 0;
  99.         while (fgets(buff, 256, stdin) && buff[0] != '\n') {
  100.             /* fprintf(stdout, "%s", buff); */
  101.             p = strtok(buff, " ");
  102.             for (j = 0; j < n; j++) {
  103.                 sscanf(p, "%d", &v);
  104.                 prefs[i][j] = v;
  105.                 p = strtok(NULL, " ");
  106.             }
  107.             i++;
  108.         }
  109.         /* fprintf(stdout, "%s", buff); */
  110.  
  111.         solve(prefs, i, j, names);
  112.  
  113.         if (cases)
  114.             fprintf(stdout, "\n");
  115.     }
  116.  
  117.     return 0;
  118. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement