Solution Notes: Perhaps the easiest way to solve this problem is to first sort the knot locations and then build an array of differences between successive locations. For example, the locations of 0, 2, 4, 6, and 10 in the sample input would be translated into the array of differences 2, 2, 2, 4. We then observe that any prefix or suffix of the difference array that is a palindrome (reads the same forward as backward) corresponds to a valid fold. For example, the prefix "2, 2" corresponds to a fold at the knot at location 2, the prefix "2, 2, 2" corresponds to a fold in between the knots at locations 2 and 4, and the suffix "4" corresponds to a fold in between the knots at locations 6 and 10. Even-length palindromes correspond to folds at knots, and odd-length palindromes correspond to folds in between two knots.

``````

#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100

int knots[MAX_N];

int intcmp(const void *p1, const void *p2)
{
int *i1 = (int *)p1;
int *i2 = (int *)p2;
return *i1 - *i2;
}

int check_palindrome(int start, int end)
{
int i;
for (i=0; start+i<=end-i; i++)
if (knots[start+i] != knots[end-i]) return 0;
return 1;
}

int main(void)
{
int N, L, i, count=0;

freopen ("folding.in", "r", stdin);
freopen ("folding.out", "w", stdout);

scanf ("%d %d", &N, &L);
for (i=0; i<N; i++)
scanf ("%d", &knots[i]);

/* Sort knots */
qsort (knots, N, sizeof(int), intcmp);

/* Convert knots array into successive differences */
for (i=0; i<N-1; i++)
knots[i] = knots[i+1] - knots[i];

/* Check left palindromes */
for (i=0; i<N-1; i++)
if (check_palindrome(0,i)) count++;

/* Check right palindromes */
for (i=1; i<N-1; i++)
if (check_palindrome(i,N-2)) count++;

printf ("%d\n", count);

return 0;
}
``````