02/10/2018, 13:59
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 ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | 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;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #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;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Có thể bạn quan tâm
0
|
