The input consists of at most 20 test cases. Each case begins with a line containing a single integer n (1 < n < 10), thenumber of paragraphs. The next line contains a permutation of 1, 2, 3, . . . , n. The last case is followed by a single zero, which should not be processed.
intgeth(int a[]){ int num = 0; for (int i = 1; i < n; ++i) if (a[i] + 1 != a[i + 1]) num++; return num; }
voidchange_para(int i, int j, int k, int a[]) { int temp1[10], temp2[10]; memcpy(temp1, a + i, sizeof(int)*j); memcpy(temp2, a + i + j, sizeof(int)*k); memcpy(a + i, temp2, sizeof(int)*k); memcpy(a + i + k, temp1, sizeof(int)*j); }
boolisok(int a[]){ for (int i = 1; i <= n; ++i) if (i != a[i]) returnfalse; returntrue; }
booldfs(int d, int paras[]){ if (d == maxd) if (isok(paras)) returntrue;
int h = geth(paras); if (3 * d + h <= 3 * maxd) for (int i = 1; i < n; ++i) for (int j = 1; j <= n - i; ++j) for (int k = 1; k <= n + 1 - i - j; ++k){ int new_para[10]; memcpy(new_para, paras, sizeof(int)* 10); change_para(i, j, k, new_para); if (dfs(d + 1, new_para)) returntrue; } returnfalse; }
intmain(){ int cas = 0; while (scanf("%d", &n) == 1 && n){ for (int i = 1; i <= n; ++i) scanf("%d", ¶[i]); for (maxd = 0; maxd < n; ++maxd) if (dfs(0, para)) break; printf("Case %d: %d\n", ++cas, maxd); } return0; }