ZOJ Problem Set - 1457
Prime Ring Problem
Time Limit: 10 Seconds
Memory Limit: 32768 KB
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.
Inputn (0 < n < 20)
OutputThe 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 Input68
Sample OutputCase 1:1 4 3 2 5 61 6 5 2 3 4
Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2
Source:
Asia 1996, Shanghai (Mainland China)
还是DFS的问题，不过需要剪枝，否则TLE。。。说实话，当16输入进去，我自己数了十多个数，程序还没完成输出，到了OJ那里竟然AC!
当输入为奇数时是无解的。WHY?因为当输入n为奇数，若素数环存在，那么素数环上的所有素数（1也算上，虽然它不是，就当广义的==！）之和和必为奇数（奇数*奇数=奇数）。然而素数环上所有素数的和是相邻各个结点和数的二倍，也就是素数环上所有素数之和是偶数=》矛盾=》素数环不存在！
BESIDES,当前一个数为奇数时，他的下一个数只能是偶数。根据奇偶性，又剪掉一些枝条。
LAST BUT NOT LEAST,其实我们只求一般的解就可以，当我们顺时针求出一个解，将它逆时针输出便得到另一个解。不过随之而来的问题是排序。如果这样，要用基数排序（我没说错吧。。。）
/*ZOJ 1457 prime ring problem
* coder:mike
* time: before breakfast
* note: 该吃饭了。。。^_^
*/
#include<stdio.h>
#define MAX 20
int flag[MAX+MAX],
prime[2*MAX]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0},
maxdepth,
ans[MAX];
int print(int n) /**< n elements */
{
int i;
for(i=0;i<n;i++)
{
printf("%d",ans[i]);
if(i<n-1)
putchar(' ');
}
putchar('/n');
return 0;
}
int dfs(int depth) /**< depth first search */
{
if(depth>maxdepth) /**< answer is found */
{
print(depth-1);
return 0;
}
int i;
if(ans[depth-2]%2==0) /**< optimize */
i=3;
else
i=2;
for(i;i<=maxdepth;i+=2)
{
if(flag[i])
continue;
if(depth<maxdepth)
{
if(!prime[i+ans[depth-2]]) /**< skip */
continue;
ans[depth-1]=i;
flag[i]=1;
dfs(depth+1);
flag[i]=0;
}
if(depth==maxdepth) /**< the last node is a little different */
{
if(!prime[i+ans[depth-2]]||!prime[1+i]) /**< skip */
continue;
ans[depth-1]=i;
flag[i]=1;
dfs(depth+1);
flag[i]=0;
}
}
return 0;
}
int main(void)
{
int ncase=1;
ans[0]=1;
flag[1]=1;
while(scanf("%d",&maxdepth)!=EOF)
{
printf("Case %d:/n",ncase++);
if(maxdepth%2) /**< no answer => skip */
{
putchar('/n');
continue;
}
dfs(2);
putchar('/n');
}
return 0;
}
