//--------------------------------------------------------------------- // 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 #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; }