Prime Ring Problem
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 13700 Accepted Submission(s): 6250
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
6 8
Sample Output
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2
Source
Recommend
JGShining
听着龙珠狂潮完成的。。兴奋。。。
1 #include2 #include 3 4 namespace ismdebug 5 { 6 using namespace std; 7 ifstream cin("in.dat", ios::in); 8 }; 9 10 //using ismdebug::cin; 11 using std::cin; 12 using std::cout; 13 using std::endl; 14 15 #define MAXN 100 16 17 int iMap[MAXN]; 18 bool iUsed[MAXN]; 19 bool iPrime[MAXN*MAXN]; 20 21 int n; 22 23 void iInit() 24 { 25 iMap[0] = 1; 26 for (int i = 0; i < MAXN; i++) 27 { 28 iUsed[i] = false; 29 } 30 iUsed[1] = true; 31 } 32 33 void iMakePrimeMap() 34 { 35 for (int i = 0; i < MAXN * MAXN; i++) 36 { 37 iPrime[i] = true; 38 } 39 40 int iCurrent = 2; 41 for (iCurrent = 2; iCurrent <= MAXN; iCurrent++) 42 { 43 if (iPrime[iCurrent] == true) 44 { 45 for (int j = iCurrent * iCurrent; j < MAXN; j += iCurrent) 46 { 47 iPrime[j] = false; 48 } 49 } 50 } 51 52 iPrime[0] = false; 53 iPrime[1] = false; 54 } 55 56 void iShowMap() 57 { 58 for (int i = 0; i < n - 1; i++) 59 { 60 cout << iMap[i] << " "; 61 } 62 if (n >= 1) 63 64 cout << iMap[n-1] << endl; 65 } 66 67 void iTry(int k) 68 { 69 if (k == n) 70 { 71 if (iPrime[iMap[0]+iMap[n-1]]) 72 { 73 iShowMap(); 74 } 75 } 76 else 77 { 78 int iNum; 79 for (iNum = 1; iNum <= n; iNum++) 80 { 81 if (!iUsed[iNum] && iPrime[iMap[k-1]+iNum]) 82 { 83 iMap[k] = iNum; 84 iUsed[iNum] = true; 85 iTry(k+1); 86 iUsed[iNum] = false; 87 } 88 } 89 } 90 } 91 92 int main() 93 { 94 iMakePrimeMap(); 95 int iCaseCount = 0; 96 while (cin >> n) 97 { 98 /*print head*/ 99 iCaseCount++;100 cout << "Case " << iCaseCount << ":" << endl;101 102 iInit();103 104 iTry(1);105 cout << endl;106 107 }108 return 0;109 }110 111 // end112 // iCoding@CodeLab