//---------------------------------------------------------------------
// Enigma1342.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "GOSH" problem from "New Scientist" magazine, 28 May 2005, page 47.
//
// Pins must be placed in a line spaced by an whole number of 
// centimeters, yet no pin can be midway between two others.
// Total distance is between 4 and 8 feet.
//---------------------------------------------------------------------

#include <stdio.h>

#define PinSpots (1 + (int) (8 * 12 * 2.54))	// Pin spots in 8 feet

int main(void)
{
	int Pins[PinSpots] = { 1, 1 };		// Pins at the 0 and 1 cm position
	int i, j, TotalPins = 2;

	// Try each pin spot in 8 feet
	for (i = 2; i < PinSpots; i++)
	{
		// Search through the previous pin spots.
		// Loop increments by 2 so midway pin spot is always an integer.
		for (j = i % 2; j < i; j += 2)
		{
			// Exit prematurely if there's a midway pin
			if (Pins[j] && Pins[(i + j) / 2])
				break;
		}

		// Increment TotalPins if the loop executed normally
		TotalPins += Pins[i] = (j >= i);
	}
	printf("Total pins = %i\n", TotalPins);
	return 0;
}