Editorial for Tổng vector


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      max=1500;
      maxs=32767;
var n,m,re,t,m1,m2,i,j,x,y,xt,yt:longint;
    a:array[0..29,0..1] of longint;
    b:array[0..14,0..1] of longint;
    p:array[0..15] of longint;
    f:array[0..maxs,0..1] of integer;
    d:array[-max..max,-max..max] of integer;

procedure rf;
var i,n:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     p[0]:=1;
     for i:=1 to 15 do p[i]:=p[i-1] shl 1;
     m:=n div 2;
     for i:=0 to m-1 do readln(a[i,0],a[i,1]);
     for i:=m to n-1 do readln(b[i-m,0],b[i-m,1]);
     read(x,y);
     dec(m);
     m1:=p[m+1]-1; m2:=p[n-n div 2]-1;
     close(input);
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     re:=0;
     d[0,0]:=1;
     for i:=1 to m1 do
     begin
          t:=i; j:=0;
          while t>0 do
          begin
               if t and 1=1 then
               begin
                    f[i,0]:=f[i,0]+a[j,0];
                    f[i,1]:=f[i,1]+a[j,1];
               end;
               inc(j);
               t:=t shr 1;
          end;
          inc(d[f[i,0],f[i,1]]);
     end;
     for i:=0 to m2 do
     begin
          t:=i; j:=0; xt:=0; yt:=0;
          while t>0 do
          begin
               if t and 1=1 then
               begin
                    xt:=xt+b[j,0];
                    yt:=yt+b[j,1];
               end;
               inc(j);
               t:=t shr 1;
          end;
          if (abs(x-xt)<=max) and (abs(y-yt)<=max) then
             re:=re+d[x-xt,y-yt];
     end;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<map>
using namespace std;

typedef pair<int, int> ii;
#define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i)
int x[33], y[33], n, a, b, u, v;
map<ii, int> m1, m2;

void backtrack(map<ii, int> &m, int begin, int end) {
    if(begin == end) ++m[ii(a, b)];
    else {
        for(int mul = 0; mul < 2; ++mul) {
            a += mul * x[begin]; b += mul * y[begin];
            backtrack(m, begin + 1, end);
            a -= mul * x[begin]; b -= mul * y[begin];
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d%d", x+i, y+i);
    scanf("%d%d", &u, &v);
    backtrack(m1, 0, n/2);
    backtrack(m2, n/2, n);
    long long res = 0;
    TR(m1, it) {
        ii f = ii(u - it->first.first, v - it->first.second);
        if(m2.count(f)) res += (long long) it->second * m2[f];
    }
    printf("%lld\n", res);
    return 0;
}

Code mẫu của ladpro98

program vectorspoj;
uses    math;
type    vector = record
        x,y:longint;
        end;
const   maxN = 30;
        maxV = 50*maxN;
        fi = '';
var     a,arr1:array[1..maxN] of vector;
        f:array[-maxV..maxV,-maxV..maxV] of longint;
        n,u,v,limit,d,res:longint;
procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        readln(inp,a[i].x,a[i].y);
        readln(inp,u,v);
        close(inp);
end;

procedure back(i,x,y:longint);
begin
        if i>limit then
        begin
                inc(d);
                arr1[d].x:=x;
                arr1[d].y:=y;
                exit;
        end;
        back(i+1,x,y);
        back(i+1,x+a[i].x,y+a[i].y);

end;

procedure sinh(i,x,y:longint);
begin
        if i>limit then
        begin
                inc(f[x,y]);
                exit;
        end;
        sinh(i+1,x,y);
        sinh(i+1,x+a[i].x,y+a[i].y);
end;

procedure process;
var     i,j:longint;
begin
        for i:=1 to d do
        begin
                inc(res,f[u-arr1[i].x,v-arr1[i].y]);
        end;

end;

begin
        input;
        limit:=n div 2;
        back(1,0,0);
        limit:=n;
        sinh(n div 2+1,0,0);
        process;
        write(res);
end.

begin
        input;
        dp;
        write(f[u,v]);
end.

Code mẫu của RR

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=30;
  MAX=32768;
type
  vector=record x,y:longint; end;
  arr=array[1..MAX] of vector;
var
  n,u,v:longint;
  kq:int64;
  a:array[1..MAXN] of vector;
  sum:array[1..2] of arr;
  d:array[1..2,1..MAX] of longint;
  sl:array[1..2] of longint;
procedure inp;
var
  f:text;
  i,sum:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n);
  for i:=1 to n do
    with a[i] do read(f,x,y);
  read(f,u,v);
  close(f);
  sum:=0;
  for i:=1 to n do sum:=sum+abs(a[i].x);
  if sum<abs(u) then begin writeln(0); halt; end;
  sum:=0;
  for i:=1 to n do sum:=sum+abs(a[i].y);
  if sum<abs(v) then begin writeln(0); halt; end;
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
procedure lietke(l,r,s:longint);
var
  x,y:longint;
  procedure visit(i:longint);
  var
    j:longint;
  begin
    for j:=0 to 1 do
      begin
        if j=1 then begin x:=x+a[i+l].x; y:=y+a[i+l].y; end;
        if i<r-l then visit(i+1)
        else
          begin
            inc(sl[s]);
            sum[s,sl[s]].x:=x;
            sum[s,sl[s]].y:=y;
          end;
        if j=1 then begin x:=x-a[i+l].x; y:=y-a[i+l].y; end;
      end;
  end;
begin
  x:=0; y:=0; sl[s]:=0;
  visit(0);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure qsort(s:longint);
var
  i,j:longint;
  procedure sort(l,r:longint);
  var
    i,j,mx,my:longint;
  begin
    i:=l; j:=r;
    with sum[s,(i+j) shr 1] do begin mx:=x; my:=y; end;
    repeat
      while (sum[s,i].x<mx) or ((sum[s,i].x=mx) and (sum[s,i].y<my)) do inc(i);
      while (sum[s,j].x>mx) or ((sum[s,j].x=mx) and (sum[s,j].y>my)) do dec(j);
      if i<=j then
        begin
          swap(sum[s,i].x,sum[s,j].x);
          swap(sum[s,i].y,sum[s,j].y);
          inc(i); dec(j);
        end;
    until i>j;
    if i<r then sort(i,r);
    if l<j then sort(l,j);
  end;
begin
  sort(1,sl[s]);
  j:=1; d[s,1]:=1;
  for i:=2 to sl[s] do
  if  (sum[s,i].x>sum[s,j].x)
  or ((sum[s,i].x=sum[s,j].x) and (sum[s,i].y>sum[s,j].y)) then
    begin
      inc(j); d[s,j]:=1;
      sum[s,j]:=sum[s,i];
    end
  else inc(d[s,j]);
  sl[s]:=j;
end;
function find(u,v,l,r:longint):longint;
var
  mid:longint;
begin
  if l>r then exit(0);
  if (u<sum[1,l].x) or ((u=sum[1,l].x) and (v<sum[1,l].y)) then exit(0);
  if (u>sum[1,r].x) or ((u=sum[1,r].x) and (v>sum[1,r].y)) then exit(0);
  if (u=sum[1,l].x) and (v=sum[1,l].y) then exit(l);
  if (u=sum[1,r].x) and (v=sum[1,r].y) then exit(r);
  mid:=(l+r) shr 1;
  if (u=sum[1,mid].x) and (v=sum[1,mid].y) then exit(mid);
  if (u<sum[1,mid].x) or ((u=sum[1,mid].x) and (v<sum[1,mid].y))
  then exit(find(u,v,1,mid-1))
  else exit(find(u,v,mid+1,r));
end;
procedure solve;
var
  i,k:longint;
begin
  for i:=1 to sl[2] do
    begin
      k:=find(u-sum[2,i].x,v-sum[2,i].y,1,sl[1]);
      if k>0 then kq:=kq+int64(d[2,i])*d[1,k];
    end;
end;
begin
  inp;
  kq:=0;
  lietke(1,n shr 1,1);
  qsort(1);
  lietke(n shr 1+1,n,2);
  qsort(2);
  solve;
  ans;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define   k  1500

int f[2*k+3][2*k+3];

int main()
{
   // freopen("VECTOR.in","r",stdin);
    int n,x[31],y[31],X,Y;
    for(int i = 0;i<=2*k;i++)
        for(int j = 0;j<=2*k;j++)
            f[i][j]=0;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d",&x[i]);
        scanf("%d",&y[i]);
    }
    scanf("%d %d",&X,&Y);
    if(X>30000 || X<-30000 || Y>30000 || Y<-30000)
    {
        printf("0");
    }
    else
    {
    int u[20];u[0]=1;
    for(int i = 1;i<=18;i++)
        u[i] = u[i-1]*2;
    int K = u[n/2]-1,M = u[n-n/2]-1;
    //printf("%d %d %d\n",n,K,M);
    //printf("************\n");
    for(int i = 0;i<=K;i++)
    {
        int N = i,tongx=0,tongy=0;
        for(int j = 1;j<=n/2;j++)
        {
            if(N%2==1)
            {
                tongx=tongx+x[j];
                tongy = tongy + y[j];
            } 
            N = N/2;
        }
       // printf("%d %d\n",tongx,tongy);
        f[tongx+k][tongy+k]++;
    }
    int KQ = 0;
    for(int i = 0;i<=M;i++)
    {
        int N = i,tongx=0,tongy=0;
        for(int j = 1;j<=n-n/2;j++)
        {
            if(N%2==1)
            {
                tongx=tongx+x[j+n/2];
                tongy = tongy + y[j+n/2];
            } 
            N = N/2;
        }
        if(X-tongx<=1500 && X-tongx>=-1500 &&   Y-tongy<=1500 && Y-tongy>=-1500)
            KQ = KQ + f[X-tongx+k][Y-tongy+k];
    }
    printf("%d",KQ);
    }
   // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program VECTOR;
const
  input  = '';
  output = '';
  maxn = 30;
  maxv = 100;
  maxs = maxn * maxv div 2;
type
  rec = record
    x,y: integer;
  end;
var
  a: array[1..maxn] of rec;
  left: array[0..(1 shl (maxn div 2)) - 1] of rec;
  p: array[-maxs..maxs,-maxs..maxs] of integer;
  s: array[0..maxn] of integer;
  ux,uy,sx,sy,n,count: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 1 to n do readln(f, a[i].x, a[i].y);
  readln(f, ux, uy);

  close(f);
end;

procedure precalc;
var
  i,j,t: integer;
begin
  left[0].x := 0;
  left[0].y := 0;

  for i := 1 to (1 shl (n div 2)) - 1 do
    for j := 1 to n div 2 do
      if i and (1 shl (j - 1)) = (1 shl (j - 1)) then
        begin
          t := i xor (1 shl (j - 1));
          left[i].x := left[t].x + a[j].x;
          left[i].y := left[t].y + a[j].y;
        end;
end;

procedure attempt(i: integer);
var
  j: integer;
begin
  for j := s[i - 1] + 1 to n do
    begin
      sx := sx + a[j].x;
      sy := sy + a[j].y;
      inc(p[sx,sy]);
      s[i] := j;

      if j < n then attempt(i + 1);
      sx := sx - a[j].x;
      sy := sy - a[j].y;
    end;
end;

function valid(kx,ky: integer): boolean;
begin
  valid := (abs(kx) <= maxs) and (abs(ky) <= maxs);
end;

procedure solve;
var
  i,kx,ky: integer;
begin
  precalc;

  sx := 0;
  sy := 0;
  fillchar(p, sizeof(p), 0);
  p[0,0] := 1;
  s[0] := n div 2;
  attempt(1);

  for i := 0 to (1 shl (n div 2)) - 1 do
    begin
      kx := ux - left[i].x;
      ky := uy - left[i].y;
      if valid(kx,ky) then count := count + p[kx,ky];
    end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, count);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
typedef pair<int,int> ii;
typedef map<ii,int> mii;
typedef vector<ii> vii;
mii a;
vii va,vb,sb;
int n;
ii v,s;
int x[22];
void init(void) {
    scanf("%d",&n);
    int i,x,y;
    for (i=1;i<=n/2;i=i+1) {
        scanf("%d",&x);
        scanf("%d",&y);
        va.push_back(ii(x,y));
    }
    for (i=n/2+1;i<=n;i=i+1) {
        scanf("%d",&x);
        scanf("%d",&y);
        vb.push_back(ii(x,y));
    }
    scanf("%d",&x);
    scanf("%d",&y);
    v=ii(x,y);
}
void btrka(int k) {
    int i;
    for (i=0;i<=1;i=i+1) {
        x[k]=i;
        s=ii(s.first+i*va[k].first,s.second+i*va[k].second);
        if (k==va.size()-1) a[s]++;
        else btrka(k+1);
        s=ii(s.first-i*va[k].first,s.second-i*va[k].second);
    }
}
void btrkb(int k) {
    int i;
    for (i=0;i<=1;i=i+1) {
        x[k]=i;
        s=ii(s.first+i*vb[k].first,s.second+i*vb[k].second);
        if (k==vb.size()-1) sb.push_back(s);
        else btrkb(k+1);
        s=ii(s.first-i*vb[k].first,s.second-i*vb[k].second);
    }
}
void process(void) {
    s=ii(0,0);
    btrka(0);
    s=ii(0,0);
    btrkb(0);
    int i;
    int cnt;
    cnt=0;
    for (i=0;i<sb.size();i=i+1)
        cnt=cnt+a[ii(v.first-sb[i].first,v.second-sb[i].second)];

    printf("%d",cnt);
}
int main(void) {
    init();
    process();
}

Code mẫu của khuc_tuan

#include <iostream>
#include <map>
using namespace std;

int n;
pair<int,int> a[33];
pair<int,int> S;

pair<int,int> operator+(pair<int,int> a, pair<int,int> b) {
    return make_pair(a.first+b.first,a.second+b.second);
}

pair<int,int> operator-(pair<int,int> a, pair<int,int> b) {
    return make_pair(a.first-b.first,a.second-b.second);
}

int main() {
    scanf("%d", &n);
    for(int i=0;i<n;++i) 
        scanf("%d%d", &a[i].first, &a[i].second);
    scanf("%d%d", &S.first, &S.second);
    if(n<=15) {
        int dem = 0;
        for(int b=0;b<(1<<n);++b) {
            pair<int,int> z = make_pair(0,0);
            for(int i=0;i<n;++i) if((b&(1<<i))!=0) z = z + a[i];
            if(z==S) ++dem;
        }
        printf("%d\n", dem);
    }
    else {
        int k = n/2;
        map<pair<int,int>,int> ma;
        for(int b=0;b<(1<<k);++b) {
            pair<int,int> z = make_pair(0,0);
            for(int i=0;i<k;++i) if((b&(1<<i))!=0) z = z + a[i];
            ma[z] ++ ;
        }
        k = n - k;
        int dem = 0;
        for(int b=0;b<(1<<k);++b) {
            pair<int,int> z = make_pair(0,0);
            for(int i=0;i<k;++i) if((b&(1<<i))!=0) z = z + a[n-1-i];
            dem += ma[S-z];
        }
        cout << dem << endl;
    }
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.