VECTOR – spoj

March 5, 2017 by Leave a Comment

Đề bài:

Thuật toán:

Code:

const
  fi='';
  fo='';
  maxn=30;
  oo=5000;
var
  d : array[-oo..oo,-oo..oo] of longint;
  x,y : array[1..maxn] of longint ;
  i,j,n,u,v,xx,yy,s1,s2 : longint;
  res : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i:=1 to n do read(x[i],y[i]);
    read(u,v);
    close(input);
  end;
procedure up1;
  begin
    inc(d[xx,yy]);
  end;
procedure try1(i : longint);
  var j: longint;
  begin
    for j:=0 to 1 do
      begin
        if j=1 then begin xx:=xx+x[i]; yy:=yy+y[i]; end;
        if i=s1 then up1 else try1(i+1);
        if j=1 then begin xx:=xx-x[i]; yy:=yy-y[i] end;
      end;
  end;
procedure up2;
  var tg1,tg2 : longint;
  begin
    tg1 := u - xx;
    tg2 := v - yy;
    if (tg1<=oo) and(tg1>=-oo) then
    if (tg2<=oo) and (tg2>=-oo) then inc(res,d[tg1,tg2]);
  end;
procedure try2(i : longint);
  var j: longint;
  begin
    for j:=0 to 1 do
      begin
        if j=1 then begin xx:=xx+x[i]; yy:=yy+y[i]; end;
        if i=n then up2 else try2(i+1);
        if j=1 then begin xx:=xx-x[i]; yy:=yy-y[i] end;
      end;
  end;
procedure process;
  begin
    s1 := n div 2; s2 := s1+1;
    xx := 0; yy:=0;
    try1(1);
    xx := 0; yy:=0;
    try2(s2);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Chủ đề: Duyệt phân tập

Thuật toán duyệt phân tập

August 21, 2016 by 1 Comment

Bài toán cơ bản: Cho mảng A[1..n] đếm số dãy con của mảng có tổng bằng S với n<=40.

  • Inp: n, S, mảng A.
  • Out: kết quả bài toán.

Inp:

4 4

1 2 3 4

Out:

2

Các dãy con: (4) , (1,3)

Phân tích: 

  • Thuật toán ta nghĩ ra ngay là duyệt dãy nhị phân 01
  • Nhưng duyệt chỉ giải quyết được với n <= 20. Chính vì vậy phải dùng thuật toán duyệt phân tập mới có thể ăn full test 🙂

Tư tưởng thuật toán duyệt phân tập:

  • Chia mảng A làm 2 mảng nhỏ độ dài n/2
  • Khi đó max(n/2)=20 => duyệt
  • Khi duyệt các mảng nhỏ ta lưu tổng các dãy con của mảng nhỏ vào các mảng riêng S1[] và S2[]
  • Với mỗi giá trị S1[] ta tìm kiếm nhị phần trong S2[] phần tử có giá trị S-S1[i] (cộng res với số gt S-S1[i] trong S2[]
  • res là kết quả bài toán

Các bài tập:

http://yeulaptrinh.de/312/coin34-spoj/
http://yeulaptrinh.de/673/vector-spoj/

Chủ đề: Duyệt phân tập, Tài liệu, Thuật toán

COIN34 – SPOJ

August 21, 2016 by 1 Comment

Đề bài: http://vn.spoj.com/problems/COIN34/

Thuật toán:

Code:

uses math;
const
  fi='';
  fo='';
  maxs=2*trunc(1e6);
  maxn=17;
var
  st,d : array[1..maxs] of longint;
  c : array[1..maxn*2] of longint;
  i,j,n,res,s1,s2,x,d1,c1,top : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
    c[1] :=2; c[2] := 3; c[3] := 5;
    for i:=4 to 34 do
      c[i] := c[i-1]+c[i-2]+c[i-3];
  end;
procedure up1;
  begin
    //if c1=x then begin res := max(res,d1); exit; end;
    //if c1>x then exit;
    inc(top); st[top] := c1;
    d[top] := d1;
  end;
procedure try1( i : longint);
  var j : longint;
  begin
    for j:=0 to 1 do
      begin
        if j=1 then begin c1 := c1+c[i]; inc(d1) end;
        if i=s1 then up1 else try1(i+1);
        if j=1 then begin c1 := c1-c[i]; dec(d1) end;
      end;
  end;
procedure up2;
  var dau,cuoi,giua,xx : longint;
  begin
    if x=c1 then begin res := max(res,d1); exit; end;
    if c1>x then exit;
    xx := x-c1;
    dau:=1;cuoi:=top;
    giua:=(dau+cuoi) div 2;
    while (giua<>dau) and (giua<>cuoi) do
      begin
        if st[giua]>=xx then cuoi :=giua else dau := giua;
        giua :=(dau+cuoi) div 2;
      end;
    for giua := dau to cuoi do
      if st[giua]=xx then break;
    if st[giua]=xx then res := max(res,d1+d[giua]);
  end;
procedure try2( i :longint);
  var j : longint;
  begin
    for j:=1 downto 0 do
      begin
        if j=1 then begin c1 := c1+c[i]; inc(d1); end;
        if i=34 then up2 else try2(i+1);
        if j=1 then begin c1 := c1-c[i]; dec(d1); end;
      end;
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs1(l,r : longint);
  var i,j,x,y : longint;
  begin
    i :=l;j:=r;
    x:=st[(l+r) div 2];
    y:=d[(l+r) div 2];
    repeat
      while (x>st[i]) or((x=st[i]) and (d[i]>y)) do inc(i);
      while (xj;
    if i
Chủ đề: Duyệt phân tập, SPOJ Mức độ: