USACO OCT08 Problem 'rotation' Analysis

by Richard Peng

Note that it's guaranteed that the N-1 edges form a connected 'path' from pulley 1 to pulley N, so it suffices to count how many belts are cross belts. This number gives a measure of how many times the rotation direction is 'inverted'. If this number is odd, the Nth pulley is rotating counterclockwise, otherwise, it's rotating clockwise.

Below is Rob Kolstad's solution:

#include <stdio.h>
#include <stdlib.h>

main () {
    FILE *fin = fopen ("rotation.in", "r");
    FILE *fout = fopen ("rotation.out", "w");

    int n, i, s, d, c;
    int flip = 0;

    fscanf (fin, "%d", &n);
    for (i = 0; i < n-1; i++) {
	fscanf (fin, "%d %d %d", &s, &d, &c);
	flip ^= c;
    }
    fprintf (fout, "%d\n", flip);
    exit (0);
}