ACM中的Prime Ring Problem,该如何解决

ACM中的Prime Ring Problem

[code=c]#include <stdio.h>
#include <string.h>
int t,n;
int p[12] = {2,3,5,7,11,13,17,19,23,29,31,37},
map[20] = {0,1,2,3,4,4,5,6,6,7,8,8,9,9,9,10,11,11,11,12},
vis[20],a[20],isp[20];

int is_prime(int e)
{
int i;
for (i = 0; i < 12; i++)
if (p[i] == e) return 1;
return 0;
}
void dfs(int cur)
{
int i,m;
if (cur == n){
if (isp[a[0]+a[cur-1]]){
for (i = 0; i < n-1; i++) printf("%d ",a[i]);
printf("%d\n",a[i]);
}
return ;
}
for (i = 1; i < t; i++){
m = p[i] - a[cur-1];
if (m > 1 && m <= n && !vis[m]){
a[cur] = m;
vis[m] = 1;
dfs(cur+1);
vis[m] = 0;
}
}
}
int main()
{
int i,cnt = 0;
a[0] = 1;
for (i = 1; i <= 2*19; i++) isp[i] = is_prime(i);
memset(vis,0,sizeof(vis)); vis[1] = 1;
while (scanf("%d",&n) == 1){
t = map[n];//t是素数p中的最大下标
printf("Case %d:\n",++cnt);
dfs(1);
printf("\n");
}
return 0;
}

[/code]
这是我写的代码，在uav上是wrong answer ,在ZOJ上是Time Limit Exceeded或Output Limit Exceeded
调试了好长时间实在是不知道怎么错了，希望高手指点一二。
[解决办法]
根据
for (i = 1; i <= 2*19; i++) isp[i] = is_prime(i);
isp的大小至少是39。
因此要把
int p[12] = {2,3,5,7,11,13,17,19,23,29,31,37},
map[20] = {0,1,2,3,4,4,5,6,6,7,8,8,9,9,9,10,11,11,11,12},
vis[20],a[20],isp[20];
中的isp[20]改为isp[39]。
[解决办法]
先前把isp[20]改为isp[39]在HDU上AC.
而UVA上不允许最后一个Case后面有空行，因此还要如下修改后在UVA上AC.

#include <stdio.h>
#include <string.h>
int t,n;
int p[12] = {2,3,5,7,11,13,17,19,23,29,31,37},
map[20] = {0,1,2,3,4,4,5,6,6,7,8,8,9,9,9,10,11,11,11,12},
vis[20],a[20],isp[39];

int is_prime(int e)
{
int i;
for (i = 0; i < 12; i++)
if (p[i] == e) return 1;
return 0;
}
void dfs(int cur)
{
int i,m;
if (cur == n){
if (isp[a[0]+a[cur-1]]){
for (i = 0; i < n-1; i++) printf("%d ",a[i]);
printf("%d\n",a[i]);
}
return ;
}
for (i = 1; i < t; i++){
m = p[i] - a[cur-1];
if (m > 1 && m <= n && !vis[m]){
a[cur] = m;
vis[m] = 1;
dfs(cur+1);
vis[m] = 0;
}
}
}
int main()
{
int i,cnt = 0;
a[0] = 1;
for (i = 1; i <= 2*19; i++) isp[i] = is_prime(i);
memset(vis,0,sizeof(vis)); vis[1] = 1;
while (scanf("%d",&n) == 1){
t = map[n];//t是素数p中的最大下标 
 
    if (cnt > 0)//加
      printf("\n");//加
printf("Case %d:\n",++cnt);
    if ((n%2) == 0)//加
  dfs(1);
//删 printf("\n");
}
return 0;
}

查看更多 下一篇