ac1153.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1153;
const
  maxn=30;
  maxa=50;
  maxs=maxa*maxn;
var
  range:array[boolean,1..maxn]of integer;
  ok:array[boolean,1..maxn,0..maxs]of boolean;
  n,i,j,a,l1,l2:shortint;
procedure move(x,y:byte);
  var
    b1,b2:boolean;
    p,t:integer;
  begin
    b2:=odd(i);b1:=not b2;
    for p:=0 to range[b1,x] do
      if ok[b1,x,p] then begin
        t:=abs(p+a);
        if t<=maxa*l2 then begin
          if t>range[b2,y] then range[b2,y]:=t;
          ok[b2,y,t]:=true;
        end;
        t:=abs(p-a);
        if t<=maxa*l2 then begin
          if t>range[b2,y] then range[b2,y]:=t;
          ok[b2,y,t]:=true;
        end;
      end;
  end;
begin
  repeat
    read(n);
    if n=0 then halt;
    fillchar(ok[true,1],sizeof(ok[true,1]),0);
    read(a);a:=abs(a);l2:=1;range[true,1]:=a;ok[true,1,a]:=true;

    for i:=2 to n*2-1 do begin
      fillchar(ok[odd(i)],sizeof(ok[odd(i)]),0);
      l1:=l2;if i>n then l2:=n*2-i else l2:=i;
      for j:=1 to l2 do begin
        range[odd(i),j]:=0;
        read(a);
        if l1<l2 then begin
          if j>1 then move(j-1,j);if j<l2 then move(j,j);
        end
        else begin
          move(j,j);move(j+1,j);
        end;
      end;
    end;

    a:=0;
    while not ok[true,1,a] do inc(a);
    writeln(a);
  until false;
end.