记录编号	13784	评测结果	AAAAAAAAAA
题目名称	[NOI 1999]棋盘分割	最终得分	100
用户昵称	Achilles	是否通过	通过
代码语言	Pascal	运行时间	0.076 s
提交时间	2009-10-10 11:13:58	内存使用	1.67 MiB

program division;
var
  n,i,j,i1,i2,i3,i4,i5,j1,j2,k1,k2:longint;
  x0:double;
  tab:array[1..8,1..8]of longint;
  sz:array[1..8,1..8,1..8,1..8,1..50]of double;
begin
  assign(input,'division.in');
  assign(output,'division.out');
  reset(input);
  rewrite(output);
  readln(n);
  x0:=0;
  for i:=1 to 8 do
  begin
    for j:=1 to 8 do
    begin
      read(tab[i,j]);
      x0:=x0+tab[i,j];
    end;
    readln;
  end;
  x0:=x0/n;
  for i1:=1 to 8 do
    for i2:=1 to 8 do
      for i3:=1 to 8 do
        for i4:=1 to 8 do
        begin
          sz[i1,i2,i3,i4,1]:=0;
          for i5:=2 to 15 do
            sz[i1,i2,i3,i4,i5]:=1.7e38;
        end;
  for i1:=1 to 8 do
    for i2:=1 to 8 do
      for i3:=i1 to 8 do
        for i4:=i2 to 8 do
        begin
          for j1:=i1 to i3 do
            for j2:=i2 to i4 do
              sz[i1,i2,i3,i4,1]:=sz[i1,i2,i3,i4,1]+tab[j1,j2];
          sz[i1,i2,i3,i4,1]:=sqr(sz[i1,i2,i3,i4,1]-x0);
        end;
  for j1:=2 to n do
    for j2:=1 to j1-1 do
      for i1:=1 to 8 do
        for i2:=1 to 8 do
          for i3:=i1 to 8 do
            for i4:=i2 to 8 do
            begin
              for k1:=i1 to i3-1 do
                if sz[i1,i2,k1,i4,j2]+sz[k1+1,i2,i3,i4,j1-j2]<sz[i1,i2,i3,i4,j1] then
                  sz[i1,i2,i3,i4,j1]:=sz[i1,i2,k1,i4,j2]+sz[k1+1,i2,i3,i4,j1-j2];
              for k2:=i2 to i4-1 do
                if sz[i1,i2,i3,k2,j2]+sz[i1,k2+1,i3,i4,j1-j2]<sz[i1,i2,i3,i4,j1] then
                  sz[i1,i2,i3,i4,j1]:=sz[i1,i2,i3,k2,j2]+sz[i1,k2+1,i3,i4,j1-j2];
            end;
  writeln(sqrt(sz[1,1,8,8,n]/n):0:3);
  close(input);
  close(output);
end.