【hdu 1016 Prime Ring Problem（巨水、、竟被PE虐，后而编程WA。怒之！！！）】

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

Asia 1996, Shanghai (Mainland China)

Recommend

JGShining

听着龙珠狂潮完成的。。兴奋。。。

  1 #include <iostream>
  2 #include <fstream>
  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 // end
112 // iCoding@CodeLab