洛谷 素数环 Prime Ring Problem

题目描述

PDF

输入格式

输出格式

题意翻译

输入正整数 nn，把整数 1,2,\dots ,n1,2,…,n 组成一个环，使得相邻两个整数之和均为素数。输出时，从整数 11 开始逆时针排列。同一个环恰好输出一次。n\leq 16n≤16，保证一定有解。

多组数据，读入到 EOF 结束。

第 ii 组数据输出前加上一行 Case i:

相邻两组数据中间加上一个空行。

输入输出样例

输入 #1复制

6
8

输出 #1复制

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4Case 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

由于本人没有注册UVA账号，但测试数据是可行的，欢迎指正。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=18;
int res[N],vis[N];
int n;
int cnt=0;
bool prime(int x){if(x<=1){return false;}for(int i=2;i<=sqrt(x);i++){if(x%i==0){return false;}}return true;
}
void dfs(int k){if(k==n+1){if(prime(res[n]+res[1])){for(int i=1;i<=n;i++){cout<<res[i]<<" ";}cout<<endl;}return;}for(int i=2;i<=n;i++){if(vis[i]){continue;}int s=i+res[k-1];if(!prime(s)){continue;}res[k]=i;vis[i]=1;dfs(k+1);vis[i]=0;}
}
int main(){ios::sync_with_stdio(false);while(cin>>n){cnt++;cout<<"Case "<<":"<<endl;res[1]=1;vis[1]=1;dfs(2);cout<<endl;}return 0;
}