[HDU 1016]--Prime Ring Problem(遡及)
10530 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1016
Prime Ring Problem
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
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.
![[HDU 1016]--Prime Ring Problem(回溯)](https://s1.md5.ltd/image/6894f204b28100677d8ca1373f2526da.gif)
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 | We have carefully selected several similar problems for you:
1010
1241
1312
1072
1242
ある整数nは、1からnまでの数字を繰り返しないようにリングに並べ、隣接する2つの数(首尾を含む)ごとの和を素数とし、素数リングと呼ぶ.
簡単にするために、各素数リングは1から始まることを規定しています.複数のテストデータがあり、各グループにn(0
解題構想:遡及する思想は、1つのdfsが完成して、最も穴のお父さんのは、1組の終わりに負けてから改行を加えなければならなくて、私は結果をプラスしてwaを提出していません.peなのに、いろいろな変更です.
完全に無愛になった、Orz~~~
コードは次のとおりです.
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 #define maxn 40
6 int vis[21], x[21], T, n;
7 int prime[maxn] = { 1, 1, 0 };
8 void init()
9 {
10 int i, j;
11 for (i = 2; i <= maxn; i++){
12 if (!prime[i]){
13 for (j = 2; i*j <= maxn; j++)
14 prime[i*j] = 1;
15 }
16 }
17 }
18
19 void dfs(int cur){
20 if (cur == n&&!prime[1 + x[n - 1]]){
21 for (int i = 0; i < n; i++){
22 if (i) cout << ' ';
23 cout << x[i];
24 }
25 cout << endl;
26 }
27 else for (int i = 2; i <= n; i++){
28 if (!vis[i] && !prime[i + x[cur - 1]]){
29 x[cur] = i;
30 vis[i] = 1;
31 dfs(cur + 1);
32 vis[i] = 0;
33 }
34 }
35 }
36
37 int main(){
38 init();
39 while (cin >> n){
40 cout << "Case " << ++T << ':' << endl;
41 if (n == 1)
42 cout << 1 << endl;
43 else if (n & 1)
44 cout << endl;
45 else{
46 memset(vis, 0, sizeof(vis));
47 x[0] = 1;
48 dfs(1);
49 }
50 cout << endl;// pe wa, , , ~~~~
51 }
52 return 0;
53 }View Code