#include #include #include int main (void) { int K, k; int p, n, i, j, bi, bj; int v[101][101], tv[101], ttv; int m, r, vj; float bp; FILE *in = fopen ("elections.in", "r"), *out = fopen("elections.out", "w"); fscanf (in, "%d\n", &K); for (k = 1; k <= K; k ++) { fprintf (out, "Data Set %d:\n", k); fscanf (in, "%d %d\n", &p, &n); for (j = 1; j <= n; j ++) for (i = 1; i <= p; i ++) { v[j][i] = 0; tv[j] = 0; } ttv = 0; for (i = 1; i <= p; i ++) { fscanf (in, "%d\n", &m); for (r = 1; r <= m; r ++) { fscanf (in, "%d %d\n", &j, &vj); v[j][i] = vj; tv[j] += vj; ttv += vj; } } printf ("\n"); while (ttv > 0) { bp = 0.0f; for (i = 1; i <= p; i ++) for (j = 1; j <= n; j ++) if (tv[j] > 0 && ((float) v[j][i]) / ((float) tv[j]) > bp + 0.000001) { bi = i; bj = j; bp = ((float) v[j][i]) / ((float) tv[j]); } ttv -= tv[bj]; tv[bj] = -bi; for (j = 1; j <= n; j ++) if (j != bj) { ttv -= v[j][bi]; tv[j] -= v[j][bi]; v[j][bi] = 0; } for (i = 1; i <= p; i ++) v[bj][i] = 0; } for (j = 1; j <= n; j ++) if (tv[j] >= 0) fprintf (out, "%d vacant\n", j); else fprintf (out, "%d %d\n", j, -tv[j]); fprintf (out, "\n"); fscanf (in, "\n"); } fclose (in); fclose (out); return 0; }