PCIRCLE spoj - Vòng số nguyên tố

Nguồn đề bài: http://vn.spoj.com/problems/PCIRCLE/

1. Đề bài PCIRCLE spoj

Một vòng tròn chứa 2*n vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ 1 đến 2*n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ 1 đến 2*n mỗi số vào một vòng tròn nhỏ sao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền ở vòng tròn nhỏ 1 luôn là số 1.

Input

Số nguyên dương n ( 1 < n < 10 ) .

Output

Dòng đầu tiên ghi ra số k là số cách tìm được.
K dòng tiếp theo mỗi dòng ghi ra 1 cách điền các số vào các vòng tròn nhỏ. Cách điền nào có thứ tự từ điển nhỏ hơn thì xếp trước. Nếu K > 10000 thì chỉ cần ghi ra 10000 cách đầu tiên.

Ví dụ

Input:
4

Output:
4
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

2. Hướng dẫn PCIRCLE spoj

– Viết sẳn thủ tục sàng số nguyên tố

– Áp dụng thuật toán quay lui để chọn các số, kiểm tra điều kiện dựa trên mảng sàng SNT.

– Vì N<10 nên có thể tính trước kết quả K và bỏ vào mảng hằng. chỉ việc xuất ra. Giúp tiết kiệm được bộ nhớ và thời gian khi quay lui.

3. code tham khảo PCIRCLE spoj

const   fi='';
        fo='';
        nmax=10;
type    data=longint;
var
        f:text;
        SNT:array[1..50] of boolean;
        n:data;

        DD:array[1..nmax*2] of boolean;
        KQ:array[1..nmax*2] of byte;
        sl:data;

        LUUTRU:array[1..16000020] of byte;
        spt,k:longint;

procedure sangnt;
var     i,j:data;
begin
        fillchar(snt,sizeof(snt),true);
        i:=2;
        snt[1]:=false;
        while i<=sqrt(50) do
                begin
                        while snt[i]=false do
                                inc(i);
                        for j:=2 to 50 div i do
                                snt[i*j]:=false;
                        inc(i);
                end;
end;

procedure init;
begin
        fillchar(dd,sizeof(dd),false);
        dd[1]:=true;
        sl:=1;
        kq[1]:=1;
        spt:=0;    k:=0;
end;

procedure xuli;
var     i:data;
begin
        if not snt[1+kq[sl]] then exit;
        inc(k);
        for i:=1 to sl do
                begin
                        inc(spt);
                        LUUTRU[spt]:=kq[i];
                end;
end;

procedure try;
var     j:data;
begin
        if sl=2*n then
                begin
                        xuli;
                end
        else
                for j:=2 to 2*n do
                        if (not dd[j]) and (SNT[kq[sl]+j]) then
                                begin
                                        dd[j]:=true;
                                        inc(sl);
                                        kq[sl]:=j;

                                        try;
                                        dd[j]:=false;
                                        dec(sl);
                                end;
end;

procedure xuat;
var     i,tam:data;
begin
        assign(f,fo); rewrite(f);
        writeln(f,k);
        if k>10000 then
                        tam:=10000*2*n
        else
                        tam:=k*2*n;

        for i:=1 to tam do
                begin
                        write(f,luutru[i],' ');
                        if i mod (2*n) = 0 then writeln(f);
                end;
        close(f);
end;

begin
        assign(f,fi); reset(f);
        readln(f,n);
        close(f);
        SANGNT;
        init;
        try;
        xuat;
end.

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

int     n,x[100],dd[100];
bool    yes[100][100];
int     res[100] = {0, 0, 2, 2, 4, 96, 1024, 2880, 81024, 770144};
int     dem = 0;

bool kt(int x)
{
    if (x <= 1) return false;
    for (int i=2;i*i<=x;i++)
        if (x % i == 0) return false;
    return true;
}

void dq(int t)
{
    if (t == n+1) {
        if (not yes[x[1]][x[n]]) return;
        dem++;
        for (int i=1;i<=n;i++) printf("%d ",x[i]);
        printf("n");
        return;
    }
    for (int i=1;i<=n;i++)
        if (dd[i] == 0 and yes[x[t-1]][i]) {
            x[t] = i;
            dd[i] = 1;
            dq(t+1);
            if (dem == 10000) return;
            dd[i] = 0;
        }
}

int main()
{
    scanf("%d",&n);
    printf("%dn",res[n]);

    n *= 2;
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++) {
            yes[i][j] = kt(i+j);
            yes[j][i] = yes[i][j];
        }

    x[1] = 1;
    dd[1] = 1;
    dq(2);

    return 0;
}

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

int     n,x[100],dd[100],res;
bool    yes[100][100];

bool kt(int x)
{
    if (x <= 1) return false;
    for (int i=2;i*i<=x;i++)
        if (x % i == 0) return false;
    return true;
}

void dq(int t)
{
    if (t == n+1) {
        if (yes[x[1]][x[n]]) res++;
        return;
    }
    for (int i=1;i<=n;i++)
        if (dd[i] == 0 and yes[x[t-1]][i]) {
            x[t] = i;
            dd[i] = 1;
            dq(t+1);
            dd[i] = 0;
        }
}

int main()
{
    scanf("%d",&n);
    n *= 2;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            yes[i][j] = kt(i+j);
    x[1] = 1;
    dd[1] = 1;
    dq(2);
    printf("%d",res);
    return 0;
}

PCIRCLE spoj – Vòng số nguyên tố