比赛 NOIP_3 评测结果 AATTAAAATA
题目名称 棋盘分割 最终得分 70
用户昵称 thegy 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-09-12 20:38:47
显示代码纯文本
program division;
var
  fin,fout:text;
  g:array[1..8,1..8]of longint;
  l:array[1..10000,1..4]of longint;
  x:array[1..20]of longint;
  n,i,j:longint;
  px,ans:real;
procedure find(x0:longint);
var
  ii,jx,jy,x1,y1,x2,y2:longint;
  nowq:real;
begin
  if x0=n then
  begin
    nowq:=0;
    for ii:=1 to n do
    begin
      x[ii]:=0;
      for jx:=l[ii,1] to l[ii,3] do
      for jy:=l[ii,2] to l[ii,4] do
        x[ii]:=x[ii]+g[jx,jy];
    end;
    for ii:=1 to n do
      nowq:=nowq+sqr(x[ii]-px);
    nowq:=sqrt(nowq/n);
    if nowq<ans then ans:=nowq;
  end else begin
             for ii:=1 to x0 do
             begin
               x1:=l[ii,1]; y1:=l[ii,2];
               x2:=l[ii,3]; y2:=l[ii,4];
               for jx:=x1 to x2-1 do
               begin
                 l[ii,3]:=jx;
                 l[x0+1,1]:=jx+1; l[x0+1,2]:=y1; l[x0+1,3]:=x2; l[x0+1,4]:=y2;
                 find(x0+1);
                 l[ii,3]:=x2;
               end;
               for jy:=y1 to y2-1 do
               begin
                 l[ii,4]:=jy;
                 l[x0+1,1]:=x1; l[x0+1,2]:=jy+1; l[x0+1,3]:=x2; l[x0+1,4]:=y2;
                 find(x0+1);
                 l[ii,4]:=y2;
               end;
             end;
           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;
  l[1,1]:=1; l[1,2]:=1; l[1,3]:=8; l[1,4]:=8;
  ans:=10000;
  find(1);
  writeln(fout,round(ans*1000)/1000:0:3);
  close(fin);
  close(fout);
end.