HDU : 1016 / UVa : 524 (Prime Ring Problem)


// http://acm.hdu.edu.cn/showproblem.php?pid=1016
// http://uva.onlinejudge.org/external/5/524.html

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <utility>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;

int n;
int a [20];
bool available [20];
int isPrime [42] = {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, 0,
                    1};

bool valid (int num, int in)
{
    if ( in == n - 1 ) {
        if (isPrime [a [in - 1] + num] && isPrime [num + 1])
            return true;
        return false;
    }
    return isPrime [a [in - 1] + num];
}

void bktk (int index)
{
    if ( index == n ) {
        printf ("%d", a [0]);
        for ( int i = 1; i < n; i++ )
            printf (" %d", a [i]);
        printf ("\n");
        return;
    }

    for ( int i = 2; i <= n; i++ ) {
        if ( available [i] ) {
            if ( valid (i, index) ) {
                available [i] = false;
                a [index] = i;
                bktk (index + 1);
                available [i] = true;
            }
        }
    }
}

int main ()
{
    int cases = 0;

    while ( scanf ("%d", &n) != EOF ) {
        a [0] = 1;

        printf ("Case %d:\n", ++cases);
        memset (available, true, sizeof (available));

        bktk (1);
        printf ("\n");
    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

2 thoughts on “HDU : 1016 / UVa : 524 (Prime Ring Problem)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s