View Code
# include# include # define N 20 + 5char ptab[25] = { 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0};int n, solu[N];bool vis[N];void dfs(int cnt){ if (cnt == n && ptab[solu[cnt]+1]) { printf("1"); for (int i = 2; i <= n; ++i) printf(" %d", solu[i]); putchar('\n'); return ; } for (int i = 2; i <= n; ++i) { if (vis[i] == false && ptab[solu[cnt]+i]) { vis[i] = true; solu[cnt+1] = i; dfs(cnt+1); vis[i] = false; } }}void solve(void){ solu[1] = 1, vis[1] = true; memset(vis+1, false, sizeof(vis[0])*n); dfs(1); putchar('\n');}int main(){ int i = 0; while (~scanf("%d", &n)) { printf("Case %d:\n", ++i); solve(); } return 0;}
Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. Note: the number of first circle should always be 1.
Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order. You are to write a program that completes above process. Print a blank line after each case.
Sample Input
68
Sample Output
Case 1:1 4 3 2 5 61 6 5 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2