HDU Prime Ring Problem

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define M 21
 5 #define sc(x) scanf("%d",&x)
 6 #define pf(x) printf("%d
",x)
 7 #define PF(x) printf("%d ",x)
 8 #define P printf("
")
 9 #define CL(x,y) memset(x, y, sizeof(x))
10 #define FOR(i,x,v) for(int i=x; i<=v; i++)
11 using namespace std;
12 int prime[12]= {3,5,7,11,13,17,19,23,29,31,37};
13 int n, arr[M], used[M];
14 void DFS(int i);
15 bool check(int x);
16 void print();
17 int main()
18 {
19     int k=1;
20     while(~sc(n))
21     {
22         CL(arr, 0);
23         CL(used, 0);
24         printf("Case %d:
",k++);
25         arr[1]=1;
26         used[1]=1;
27         DFS(2);
28         P;
29     }
30     return 0;
31 }
32 bool check(int x)
33 {
34     for(int k = 0; k < 11; k++)
35         if(prime[k] == x)
36             return true;
37     return false;
38 }
39 void print()
40 {
41     FOR(i, 1, n-1)//for(int i=1; i<n; i++)
42     PF(arr[i]);
43     pf(arr[n]);
44 }
45 void DFS(int i)
46 {
47     if(i == n+1)
48         print();
49     else
50     {
51         FOR(j, 2, n)// for(int j = 2; j<= n; j++)
52         {
53             if(i == n)
54             {
55                 if(!used[j] && check(j + arr[i-1]) && check(j + arr[1]))
56                 {
57                     used[j] = 1;
58                     arr[i] = j;
59                     DFS(i+1);
60                     used[j] = 0;
61                 }
62             }
63             else
64             {
65                 if(!used[j] && check(j + arr[i-1]))
66                 {
67                     used[j] = 1;
68                     arr[i] = j;
69                     DFS(i+1);
70                     used[j] = 0;
71                 }
72             }
73         }
74     }
75 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #define sc(x) scanf("%d",&x)
 6 #define pf(x) printf("%d
",x)
 7 #define PF(x) printf("%d",x)
 8 #define CL(x,y) memset(x,y,sizeof(x))
 9 using namespace std;
10 int prime[12]= {3,5,7,11,13,17,19,23,29,31,37};
11 const int MAX = 20;
12 int n;
13 int arr[MAX], used[MAX];
14 void DFS(int num);
15 bool check(int x);
16 int main()
17 {
18     int k = 1;
19     while(sc(n)!=EOF)
20     {
21         printf("Case %d:
", k++);
22         CL(used, 0);
23         CL(arr, 0);
24         arr[1] = 1;
25         used[1] = 1;
26         DFS(2);
27         cout << endl;
28     }
29     return 0;
30 }
31 void DFS(int num)
32 {
33     if(num > n)
34     {
35         for(int i = 1; i <= n; i++)
36         {
37             printf("%d", arr[i]);
38             if(i < n) printf(" ");
39         }
40         cout << endl;
41     }
42     else
43         for(int j = 2; j <= n; j++)
44         {
45             if(num <= n-1)
46             {
47                 if((arr[num-1]+j)&1 && !used[j] && check(arr[num-1]+j))
48                 {
49                     used[j] = 1;
50                     arr[num] = j;
51                     DFS(num+1);
52                     used[j] = 0;
53                 }
54             }
55             else
56             {
57                 if((arr[num-1]+j)&1 && !used[j] && check(j+arr[1]) && check(arr[num-1]+j))
58                 {
59                     used[j] = 1;
60                     arr[num] = j;
61                     DFS(num+1);
62                     used[j] = 0;
63                 }
64             }
65         }
66 }
67 bool check(int x)
68 {
69     int j;
70     for(j = 3; j * j <= x; j++)
71     {
72         if(x % j == 0)
73             return false;
74     }
75     return true;
76 }
77 //bool check(int x)
78 //{
79 //    for(int k = 0; k < 11; k++)
80 //        if(prime[k] == x)
81 //            return true;
82 //    return false;
83 //}

View Code