UVA 524 - Prime Ring Problem

A ring is composed of n (even number) circles as shown in diagram. Put natural numbers  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 <= 16)

 

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.

 

You are to write a program that completes above process.

 

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

 

最后只能输出一行空行！否则WA

每行的最后不能有空格，否则PE

 

#define RUN
#ifdef RUN

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <assert.h>  
#include <string>  
#include <iostream>  
#include <sstream>  
#include <map>  
#include <set>  
#include <vector>  
#include <list>  
#include <cctype>   
#include <algorithm>  
#include <utility>  
#include <math.h>  
#include <ctime>  
using namespace std;

bool noAnswer;
int cases = 1;
#define MAXN 10000

int is_prime(int x) {
  for(int i = 2; i*i <= x; i++)
    if(x % i == 0) return 0;
  return 1;
}

int n, A[MAXN],	// A数组用于保存结果 A[x]=y 第x个位置放了大小为y的数
	isp[MAXN],	// isp数组用于判断是否素数 isp[x]=y 大小为x的数，其素数属性为y
	vis[MAXN];	// vis数组用于标示第i个数是否已经被使用过了 vis[x]=y，大小为x的数，已使用性为y

void dfs(int cur) {

  //递归边界，同时测试第一个数和最后一个数
  if(cur == n && isp[A[0]+A[n-1]]) {
	  noAnswer = false;
	  printf("%d", A[0]);
	  for(int i = 1; i < n; i++){
		  printf(" %d", A[i]);
	  }
      printf("\n");
  }
  else {
	  for(int i = 2; i <= n; i++){
		  if(!vis[i] && isp[i+A[cur-1]]) {
			  A[cur] = i;	//标志把数i放在cur的位置上
			  vis[i] = 1;	//标志i已经用了
			  dfs(cur+1);	//寻找下一个位置应该放的数
			  vis[i] = 0;	//还原全局变量，清除标志
		  }
	  }
  }

}


int main() {

#ifndef ONLINE_JUDGE
	freopen("524.in", "r", stdin);
	freopen("out.out", "w", stdout); 
#endif

	//生成素数表，加快后面的判断
	//判断第i个数是否是素数，如果isp[i]返回1则是，返回0则否
	memset(isp, 0, sizeof(isp));
	//isp[2] = isp[3] = isp[5] = isp[7] = isp[11] = isp[13] = isp[17] = isp[19] = isp[23] = isp[29] = isp[31] = isp[37] = 1;
	for(int i = 2; i <= 20*2; i++){
		isp[i] = is_prime(i);
	}

	A[0] = 1;
	bool isprint = false;

	while(scanf("%d",&n) != EOF){

		//Remove last duplicate line
		if(isprint){
			printf("\n");
		}
		isprint = true;
		noAnswer = true;
		cout << "Case " << cases << ":" << endl;
		cases++;

		memset(vis, 0, sizeof(vis));

		//自环的情况
		if(n==1) { printf("%d\n",A[0]); continue;}            

		//重要的剪枝！！！
		//如果n为奇数，存在不等于2的偶数，不为素数，可以直接排除
		// 奇+偶=奇
		// 奇+奇=偶
		// 偶+偶=偶
		if(n%2 != 0) { printf("No Answer\n"); continue;}        

		dfs(1);
		if(noAnswer){
			cout << "No Answer" << endl;
		}
		
	}


  return 0;
}

#endif