记录编号	2127	评测结果	AAAAAAAAAW
题目名称	[NOI 1999]棋盘分割	最终得分	90
用户昵称	thegy	是否通过	未通过
代码语言	Pascal	运行时间	0.752 s
提交时间	2008-09-12 22:40:18	内存使用	0.52 MiB

program division2;
var
  n,i,j,ii,jj,k:longint;
  px,ans:real;
  fin,fout:text;
  g:array[1..8,1..8]of longint;
  v,vv:array[1..8,1..8,1..8,1..8,1..20]of boolean;
  f:array[1..8,1..8,1..8,1..8,1..20]of longint;
procedure dp(x1,y1,x2,y2,x0:longint);
var
  i1,j1,kk,t,tt:longint;
  flag:boolean;
begin
  if x0=1 then
  begin
    tt:=0;
    for i1:=x1 to x2 do
    for j1:=y1 to y2 do
      tt:=tt+g[i1,j1];
    f[x1,y1,x2,y2,1]:=tt*tt;
    v[x1,y1,x2,y2,1]:=true;
    vv[x1,y1,x2,y2,1]:=true;
    if (x1=1) and (y1=1) and (x2=8) and (y2=3) then writeln(tt);
  end else begin
             flag:=false;
             f[x1,y1,x2,y2,x0]:=maxlongint;
             for kk:=1 to x0-1 do
             begin
               for i1:=x1 to x2-1 do
               begin
                 if not(v[x1,y1,i1,y2,kk]) then dp(x1,y1,i1,y2,kk);
                 if not(v[i1+1,y1,x2,y2,x0-kk]) then dp(i1+1,y1,x2,y2,x0-kk);
                 if vv[x1,y1,i1,y2,kk] and vv[i1+1,y1,x2,y2,x0-kk] then
                 begin
                   flag:=true;
                   t:=f[x1,y1,i1,y2,kk]+f[i1+1,y1,x2,y2,x0-kk];
                   if t<f[x1,y1,x2,y2,x0] then f[x1,y1,x2,y2,x0]:=t;
                 end;
               end;
               for j1:=y1 to y2-1 do
               begin
                 if not(v[x1,y1,x2,j1,kk]) then dp(x1,y1,x2,j1,kk);
                 if not(v[x1,j1+1,x2,y2,x0-kk]) then dp(x1,j1+1,x2,y2,x0-kk);
                 if vv[x1,y1,x2,j1,kk] and vv[x1,j1+1,x2,y2,x0-kk] then
                 begin
                   flag:=true;
                   t:=f[x1,y1,x2,j1,kk]+f[x1,j1+1,x2,y2,x0-kk];
                   if t<f[x1,y1,x2,y2,x0] then f[x1,y1,x2,y2,x0]:=t;
                 end;
               end;
             end;
             if flag then vv[x1,y1,x2,y2,x0]:=true else vv[x1,y1,x2,y2,x0]:=false;
           end;
end;
begin
  assign(fin,'division.in'); reset(fin);
  assign(fout,'division.out'); rewrite(fout);
  read(fin,n);
  px:=0;
  for i:=1 to 8 do
  for j:=1 to 8 do
  begin
    read(fin,g[i,j]);
    px:=px+g[i,j];
  end;
  px:=px/n;
  for i:=1 to 8 do
  for j:=1 to 8 do
  for ii:=1 to 8 do
  for jj:=1 to 8 do
  for k:=1 to n do
  begin v[i,j,ii,jj,k]:=false; vv[i,j,ii,jj,k]:=false; end;
  dp(1,1,8,8,n);
  ans:=sqrt(f[1,1,8,8,n]/n-sqr(px));
  writeln(fout,round(ans*1000)/1000:0:3);
  close(fin);
  close(fout);
end.