USACO MAR09 Problem 'perfect' Analysis

by Rob Kolstad

This program has a sort subprogram (the simplest of all possible exchange sorts, not even as fast as a bubble sort) which is exploited to find the median of the input rows and then the median of the medians, each time by choosing the middle element of the sorted list.

#include <stdio.h>

int medians[1000], n;

sortem(x)
    int x[];
{
    int j, k;
    for (j = 0; j < n; j++)
        for (k = j+1; k < n; k++) {
            if (x[j] > x[k]) {
                int t = x[j];
                x[j] = x[k];
                x[k] = t;
            }
        }
}

main () {
    FILE *fin = fopen ("perfect.in", "r");
    FILE *fout = fopen ("perfect.out", "w");
    int i, j, beauty[1000];
    fscanf (fin, "%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)  {
            fscanf (fin, "%d", &beauty[j]);
        }
        sortem (beauty);
        medians[i] = beauty[n/2];
    }
    sortem (medians);
    fprintf (fout, "%d\n", medians[n/2]);
    exit (0);
}