USACO OCT07 Problem 'squares' Analysis

by Rob Kolstad

This solution is the simplest of brute-force searches. N is 500, so we know that we will do no more than 500*500=250,000 operations (and actually just half that), which is more than doable in 1.0 CPU seconds (in fact, this program runs in under 4 milliseconds for all the test data).

The double nested loop carefully checks all the possible (a,b) combinations, being careful not to double count.

#include <stdio.h>
 
main() {
    int a, b, diff, count;
    FILE *fin = fopen ("squares.in", "r");
    FILE *fout = fopen ("squares.out", "w");
    count = 0;
    fscanf (fin, "%d", &diff);
    for (a = 1; a <= 500; a++)
        for (b = a+1; b <= 500; b++)
            if (b*b - a*a == diff)
                count++;
    fprintf (fout, "%d\n", count);
    exit (0);
}