gdoi200012.pas

   1 type
   2         arr=array [-5000..5000] of longint;
   3
   4 var
   5         a,b:array [-5000..5000] of longint;
   6         domino:array [0..1000] of longint;
   7         i,j,p,q,n:longint;
   8
   9 function min(a,b:longint):longint;
  10 begin
  11         if a<b then exit(a) else exit(b);
  12 end;
  13
  14 procedure swap(var a,b:arr);
  15 var
  16         t:arr;
  17
  18 begin
  19         t:=a; a:=b; b:=t;
  20 end;
  21
  22 begin
  23         readln(n);
  24         for i:=1 to n do
  25                 begin
  26                         readln(p,q);
  27                         domino[i]:=p-q;
  28                 end;
  29         for i:=-5000 to 5000 do begin a[i]:=maxint; b[i]:=maxint; end;
  30         p:=0; q:=0; a[0]:=0;
  31         for i:=1 to n do
  32                 begin
  33                         for j:=p to q do
  34                                 if a[j]<maxint then
  35                                         begin
  36                                                 b[j+domino[i]]:=min(a[j],b[j+domino[i]]);
  37                                                 b[j-domino[i]]:=min(a[j]+1,b[j-domino[i]]);
  38                                                 a[j]:=maxint;
  39                                         end;
  40                         p:=p-abs(domino[i]);
  41                         q:=q+abs(domino[i]);
  42                         swap(a,b);
  43                 end;
  44         for i:=0 to n do
  45                 if (a[i]<>maxint) or (a[-i]<>maxint) then break;
  46         writeln(min(a[i],a[-i]));
  47 end.