Nguồn đề bài: http://vn.spoj.com/problems/VECTOR/
1. Đề bài VECTOR spoj
Trong mặt phẳng tọa độ có N véc tơ. Mỗi một véc tơ được cho bởi hai chỉ số x và y. Tổng của hai véc tơ (xi, yi) và (xj, yj) được định nghĩa là một véc tơ (xi + xj, yi + yj). Bài toán đặt ra là cần chọn một số véc tơ trong N véc tơ đã cho sao cho tổng của các vec tơ đó là véc tơ (U, V).
Yêu cầu: Đếm số cách chọn thoả mãn yêu cầu bài toán đặt ra ở trên.
Input
Dòng thứ nhất ghi số N (0 ≤ N ≤ 30).
N dòng tiếp theo, dòng thứ i ghi các số nguyên xi, yi lần lượt là hai chỉ số của véc tơ thứ i. (|xi|, |yi| ≤ 100).
Dòng cuối cùng ghi số hai số nguyên U V (|U|, |V| ≤ 109).
Output
Gồm một số duy nhất là số cách chọn thoả mãn.
Example
Input:
4
0 0
-1 2
2 5
3 3
2 5
Output:
4
2. Hướng dẫn VECTOR spoj
Nếu duyệt tổ hợp của N Vector thì độ phức tạp thuật toán là O(2^N), với n=30 thì không thể ăn hết điểm của bài này. Vì vậy cần giảm N xuống, thay bằng thuật toán duyệt phân tập (duyệt bằng cách chia đôi tập hợp – trong tập “Một số vấn đề trong tin học” hoặc KCBOOK) :
- Chia tập hợp thành 2 tập con là A và B.
- Duyệt tập A dùng mảng F[i,j] để đếm số cách chọn những vector từ A đề được tổng (i, j).
- Duyệt tiếp tập B, với mỗi tổng (a, b) thu được, ta cộng vào biến Res (Result) theo công thức : Res := Res + f[u-a, v-b];
- Biến res chính là kết quả bài toán.
3. Code tham khảo VECTOR spoj
* Admin đã bổ sung thêm code mẫu 27/06/2015
a. Code pascal 1
const
maxn = 30;
maxc = 3000;
type
TVector = record
x, y : longint
end;
var
n, u, v,
res : longint;
vec, t : array[0..maxn] of TVector;
f : array[-3000..3000, -3000..3000] of longint;
procedure enter;
var fi : text;
i : longint;
begin
assign(fi, ''); reset(fi);
readln(fi, n);
for i:= 1 to n do
with vec[i] do
readln(fi, x, y);
readln(fi, u, v);
close(fi)
end;
procedure process1(i : longint);
var j : byte;
begin
for j:= 0 to 1 do
begin
t[i].x:= t[i-1].x;
t[i].y:= t[i-1].y;
if j=1 then
begin
t[i].x:= t[i].x + vec[i].x;
t[i].y:= t[i].y + vec[i].y
end;
if i <= n div 2 then
if i < n div 2 then
process1(i+1)
else inc(f[t[i].x, t[i].y]);
end;
end;
procedure process2(i : longint);
var j : byte;
begin
for j:= 0 to 1 do
begin
t[i].x:= t[i-1].x;
t[i].y:= t[i-1].y;
if j=1 then
begin
t[i].x:= t[i].x + vec[i].x;
t[i].y:= t[i].y + vec[i].y
end;
if i <= n then
if i < n then
process2(i+1)
else inc(res, f[u-t[i].x, v-t[i].y])
end
end;
begin
enter;
if (u>3000) or (v>3000) then
writeln(0)
else begin
process1(1);
with t[n div 2] do
begin
x:= 0; y:= 0
end;
process2(n div 2 + 1);
writeln(res);
end;
readln
end.b. Code pascal 2
Code của admin
const fi='';
nmax=30;
type data=longint;
var
f:text;
B:array[-3000..3000,-3000..3000] of word;
ax,ay:array[0..nmax+1] of data;
uu,vv,n,res:data;
procedure try1(i,u,v:data);
begin
if i>n div 2 then exit;
try1(i+1,u+ax[i],v+ay[i]);
inc(b[u+ax[i],v+ay[i]]);
try1(i+1,u,v);
end;
procedure try2(i,u,v:data);
begin
if i>n then exit;
res:=res+b[uu-(u+ax[i]),vv-(v+ay[i])];
try2(i+1,u+ax[i],v+ay[i]);
try2(i+1,u,v);
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n);
fillchar(b,sizeof(b),0);
for i:=1 to n do
readln(f,ax[i],ay[i]);
readln(f,uu,vv); b[0,0]:=1;
close(f);
end;
begin
docfile;
try1(1,0,0);
res:=B[uu,vv];
try2(n div 2+1,0,0);
writeln(res);
end.
