02/10/2018, 14:04
VECTOR spoj – Tổng Vector
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ơ (x i , y i ) và (x j , y j ) được định nghĩa là một véc tơ (x i + x j , y i + y j ). Bài toán đặt ra là ...
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.
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 | 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.
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 | 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. |
