ACCEPTED !!! A copy of this one was the opener at Coimbatore regionals 2006/07.
Its infact a simple BACKTRACKING problem
____________________________________________________________________
Question: Prime Ring Problem
____________________________________________________________________
#include "iostream.h"
#include "stdio.h"
int n, mat[17][16], isprime[32];
char seq[16];
bool used[17];
int isPrime(int n) {
for(int i = 2; i < i ="="">
return 1;
}
void permute(int count) {
if(count == n && isprime[seq[0] + seq[n-1]]) {
for(int i = 0; i <>
if(i > 0) printf(" ");
printf("%d", seq[i]);
}
printf("\n");
return;
}
int last = seq[count-1];
int non = mat[last][0];
for(int i = 1; i <= non; i++) {
int next = mat[last][i];
if((next - count) % 2 != 0 && used[next] != 1) {
used[next] = true;
seq[count] = next;
permute(count + 1);
used[next] = false;
}
}
}
int main()
{
for(int i = 3; i <= 31; i++ ) isprime[i] = isPrime(i);
seq[0] = 1;
used[1] = true;
int t = 1;
while(cin >> n) {
if(t > 1) cout <<>
cout << "Case " <<>
t++;
if(n % 2 == 1) continue;
for(int i = 1 ; i <= n; i++) {
int c = 0;
for(int j = 2; j <= n; j++) if(isprime[i+j]) mat[i][++c] = j;
mat[i][0] = c;
}
permute(1);
}
return 0;
}
____________________________________________________________________
Sunday, December 16, 2007
Prime Ring problem
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment