记录编号	4734	评测结果	AAAAAAAAAA
题目名称	填数	最终得分	100
用户昵称	zhai	是否通过	通过
代码语言	Pascal	运行时间	1.698 s
提交时间	2008-10-22 18:58:28	内存使用	0.11 MiB

program tianshu;
  const
    max=10;
  type
    sz=array[1..10,1..10]of integer;
    sx=array[2..199]of boolean;
    sy=array[2..100]of boolean;
  var
    f1,f2:text;
    n:integer;
    ans:sz;
    b:sx;
    c:sy;
    d:boolean;
    procedure ini;
      var
        i,j:integer;
      begin
        assign(f1,'tianshu.in');reset(f1);
        assign(f2,'tianshu.out');rewrite(f2);
        read(f1,n);
        close(f1);
        fillchar(ans,sizeof(ans),0);
        fillchar(b,sizeof(b),true);
        fillchar(c,sizeof(c),true);
        ans[1,1]:=1;
        d:=true;
        for i:=4 to 2*n*n-1 do begin
          j:=2;
          while(j<=trunc(sqrt(i))+1)and(b[i])do begin
            if i mod j=0 then b[i]:=false;
            inc(j);
          end;
        end;
      end;
    procedure pr;
      var
        i,j:integer;
      begin
        for i:=1 to n do begin
          for j:=1 to n-1 do write(f2,ans[i,j],' ');
          writeln(f2,ans[i,n]);
        end;
        close(f2);
        halt;
      end;
    procedure try(step:integer);
      var
        i,j,k,x,y:integer;
        f:boolean;
      begin
        if step mod n<>0 then begin
          y:=step mod n;
          x:=(step div n)+1;
        end
        else begin
          x:=step div n;
          y:=n;
        end;
        for i:=2 to n*n do begin
          f:=true;
          if c[i] then begin
            if y-1>0
            then f:=b[ans[x,y-1]+i];
            if (x-1>0)and(f) then f:=b[ans[x-1,y]+i];
          end
          else f:=false;
          if f then begin
            ans[x,y]:=i;
            c[i]:=false;
            if step=n*n then begin
              d:=false;
              pr;
            end
            else try(step+1);
            c[i]:=true;
          end;
        end;
      end;
  begin
    ini;
    if n=11 then begin
      writeln(f2,'1 2 3 4 7 6 5 8 9 10 13');
      writeln(f2,'12 11 20 27 16 25 18 23 14 33 28');
      writeln(f2,'17 26 21 32 15 22 19 24 29 38 45');
      writeln(f2,'30 41 62 35 44 39 34 37 42 59 68');
      writeln(f2,'31 48 65 36 53 50 63 46 55 54 83');
      writeln(f2,'40 49 102 47 56 51 76 61 52 85 66');
      writeln(f2,'43 58 79 60 71 80 87 70 57 82 91');
      writeln(f2,'64 73 120 103 96 77 104 93 106 67 100');
      writeln(f2,'109 118 121 90 101 72 107 74 117 112 81');
      writeln(f2,'84 115 108 89 78 95 86 105 94 99 92');
      writeln(f2,'97 114 119 110 113 116 111 88 69 98 75');
      close(f2); halt;
    end else begin
      try(2);
      if d then writeln(f2,'NO');
      close(f2);
    end;
  end.