记录编号	5163	评测结果	AATTAAAATA
题目名称	[NOI 1999]棋盘分割	最终得分	70
用户昵称	zhai	是否通过	未通过
代码语言	Pascal	运行时间	6.652 s
提交时间	2008-10-25 13:17:53	内存使用	0.11 MiB

program division;
  const
    max=8;
  type
    sz=array[1..8,1..8]of integer;
    sx=record
      x1,x2,y1,y2:integer;
    end;
    zz=array[1..20]of sx;
  var
    f1,f2:text;
    n:integer;
    i:integer;
    a:sz;
    e:zz;
    ans:real;
    procedure ini;
      var
        i,j:integer;
      begin
        assign(f1,'division.in');reset(f1);
        assign(f2,'division.out');rewrite(f2);
        readln(f1,n);
        fillchar(a,sizeof(a),0);
        for i:=1 to 8 do
          for j:=1 to 8 do
            read(f1,a[i,j]);
        close(f1);
        ans:=9999999;
        e[1].x1:=1;e[1].y1:=1;
        e[1].x2:=8;e[1].y2:=8;
      end;
    procedure jisuan(var f:real;b:zz);
      var
        j,k,h:integer;
        nz:array[1..15]of integer;
        ny:array[1..15]of real;
        nx:integer;
        xb:real;
      begin
        f:=0;
        nx:=0;
        fillchar(nz,sizeof(nz),0);
        for h:=1 to n do
          for j:=b[h].x1 to b[h].x2 do
            for k:=b[h].y1 to b[h].y2 do inc(nz[h],a[j,k]);
        for h:=1 to n do inc(nx,nz[h]);
        xb:=nx/n;
        fillchar(ny,sizeof(ny),0);
        for j:=1 to n do begin
          ny[j]:=(nz[j]-xb)*(nz[j]-xb);
          f:=ny[j]+f;
        end;
      end;
    procedure try(step:integer;b:zz);
      var
        i,j,k:integer;
        f:real;
        temp:sx;
      begin
        if step=n then begin
          jisuan(f,b);
          if f<ans then
            ans:=f;
        end
        else begin
          for k:=1 to step do begin
            temp:=b[k];
            for i:=b[k].x1+1 to b[k].x2 do begin
              b[step+1].x1:=i;
              b[step+1].y1:=b[k].y1;
              b[step+1].x2:=b[k].x2;
              b[step+1].y2:=b[k].y2;
              b[k].x2:=i-1;
              try(step+1,b);
              b[k].x2:=temp.x2;
            end;
            for j:=b[k].y1+1 to b[k].y2 do begin
              b[step+1].y1:=j;
              b[step+1].x1:=b[k].x1;
              b[step+1].x2:=b[k].x2;
              b[step+1].y2:=b[k].y2;
              b[k].y2:=j-1;
              try(step+1,b);
              b[k].y2:=temp.y2;
            end;
          end;
        end;
      end;
  begin
    ini;
    try(1,e);
    ans:=ans/n;
    ans:=sqrt(ans);
    writeln(f2,ans:0:3);
    close(f2);
  end.