UVa 524 - Prime Ring Problem



#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <bitset>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef std::vector<int> vi;
typedef std::vector<pair<int, int> > vii;
//----------Main source code -----------------//
int n, ring[17];
bitset<32> prime;
bitset<17> state;

void rcr(int i){
 if(i==n-1){
  if(prime[1+ring[i-1]]){
   cout<<ring[0];
   for(int j=1;j<n-1;j++)
    cout<<" "<<ring[j];
   cout<<endl;
  }
 }
 for(int j=2;j<n;j++)
  if(state[j]&&prime[ring[i-1]+j]){
   ring[i]=j;
   state.reset(j);
   rcr(i+1);
   state.set(j);
  }
}
int main() {
 //-prime sieve-------
 prime.set();
 for(int i=2;i<32;i++)
  if(prime[i])
   for(int j=2*i;j<32;j+=i)
    prime.reset(j);

 int ca =1;
 while(cin.good()&&cin>>n){
  n++;
  state.set();
  ring[0]=1;
  if(ca!=1) cout<<endl;
  printf("Case %d:\n", ca++);
  rcr(1);
 }
 return 0;
}
Runtime:0.522
Ideone: http://ideone.com/uylcK8
Note: you might be getting WA instead PRE due to line breaks

Comments

Popular Posts