January 2006 Problem 'stumps' Analysis

by Bruce Merry

This is a simple problem made to sound harder than it really is. Any stump that is at least as tall as both its neighbours cannot be destroyed indirectly, so Farmer John will have to dynamite them. Conversely, blowing up all these peak stumps will destroy all the stumps. So you simply need to count the number of peak stumps.

/* RBK solution */
#include <stdio.h>

int height[50000];
int nstumps;

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

    fscanf (fin, "%d", &nstumps);
    for (i = 0; i < nstumps; i++)
	fscanf (fin, "%d", &height[i]);
    for (i = 0; i < nstumps; i++) {
	if (i > 0 && height[i-1] > height[i]) continue;
	if (i < nstumps-1 && height[i+1] > height[i]) continue;
	fprintf (fout, "%d\n", i+1);
    }
    exit (0);
}