prime3.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:prime3
}

program prime3;
const
  row:array[1..13]of byte=(1,2,3,4,5,5,5,2,3,2,1,1,2);
  col:array[1..13]of byte=(5,5,5,5,4,3,2,2,3,4,2,3,1);
  range:array[1..5,1..5]of string=
        (('','123456789','123456789','123456789','1379'),
         ('123456789','0123456789','0123456789','0123456789','1379'),
         ('123456789','0123456789','0123456789','0123456789','1379'),
         ('123456789','0123456789','0123456789','0123456789','1379'),
         ('1379','1379','1379','1379','1379'));
var
  fin,fout:text;
  prime:array[2..99999]of boolean;
  map:array[1..5,1..5]of integer;
  sol:array[1..1000]of string[25];
  t:string[25];
  sum:byte;
  sols,i,j:integer;
procedure calprime;
  var
    i,j,t:longint;
    x:string[5];
  begin
    fillchar(prime,sizeof(prime),1);
    for i:=2 to trunc(sqrt(99999)) do
      if prime[i] then
        for j:=2 to 99999 div i do
          prime[i*j]:=false;

    for i:=10000 to 99999 do
      if prime[i] then begin
        str(i,x);
        t:=0;
        for j:=1 to 5 do
          t:=t+ord(x[j])-48;
        if t<>sum then prime[i]:=false;
      end;
  end;
function ch(x,y:byte):char;
  begin
    ch:=chr(48+map[x,y]);
  end;
function value(s:string):longint;
  var
    junk:word;
  begin
    val(s,value,junk);
  end;
procedure save;
  var
    i,j:byte;
  begin
    inc(sols);
    sol[sols]:='';
    for i:=1 to 5 do
      for j:=1 to 5 do
        sol[sols]:=sol[sols]+ch(i,j);
  end;
procedure search(l:byte);
  var
    i:byte;
    ok:boolean;
  function inrange(x,y:byte):boolean;
    begin
      inrange:=(pos(ch(x,y),range[x,y])>0);
    end;
  function okrow(r:byte):boolean;
    begin
      okrow:=prime[value(ch(r,1)+ch(r,2)+ch(r,3)+ch(r,4)+ch(r,5))];
    end;
  function okcol(c:byte):boolean;
    begin
      okcol:=prime[value(ch(1,c)+ch(2,c)+ch(3,c)+ch(4,c)+ch(5,c))];
    end;
  function okdiag1:boolean;
    begin
      okdiag1:=prime[value(ch(1,1)+ch(2,2)+ch(3,3)+ch(4,4)+ch(5,5))];
    end;
  function okdiag2:boolean;
    begin
      okdiag2:=prime[value(ch(5,1)+ch(4,2)+ch(3,3)+ch(2,4)+ch(1,5))];
    end;
  procedure check12;
    begin
      ok:=false;
      map[1,4]:=sum-map[1,1]-map[1,2]-map[1,3]-map[1,5];
      if not inrange(1,4) then exit;
      if not okrow(1) then exit;
      map[3,4]:=sum-map[1,4]-map[2,4]-map[4,4]-map[5,4];
      if not inrange(3,4) then exit;
      if not okcol(4) then exit;
      map[3,1]:=sum-map[3,2]-map[3,3]-map[3,4]-map[3,5];
      if not inrange(3,1) then exit;
      if not okrow(3) then exit;
      ok:=true;
    end;
  procedure check13;
    begin
      ok:=false;
      map[2,3]:=sum-map[2,1]-map[2,2]-map[2,4]-map[2,5];
      if not inrange(2,3) then exit;
      if not okrow(2) then exit;
      map[4,1]:=sum-map[1,1]-map[2,1]-map[3,1]-map[5,1];
      if not inrange(4,1) then exit;
      if not okcol(1) then exit;
      map[4,3]:=sum-map[4,1]-map[4,2]-map[4,4]-map[4,5];
      if not inrange(4,3) then exit;
      if not okrow(4) then exit;
      if not okcol(3) then exit;
      ok:=true;
    end;
  begin
    for i:=1 to length(range[row[l],col[l]]) do begin
      map[row[l],col[l]]:=ord(range[row[l],col[l]][i])-48;
      ok:=true;
      case l of
        4:begin
            map[5,5]:=sum-map[1,5]-map[2,5]-map[3,5]-map[4,5];
            ok:=inrange(5,5);
            if ok then ok:=okcol(5);
          end;
        7:begin
            map[5,1]:=sum-map[5,2]-map[5,3]-map[5,4]-map[5,5];
            ok:=inrange(5,1);
            if ok then ok:=okrow(5);
          end;
        9:begin
            map[4,4]:=sum-map[1,1]-map[2,2]-map[3,3]-map[5,5];
            ok:=inrange(4,4);
            if ok then ok:=okdiag1;
          end;
        10:begin
             map[4,2]:=sum-map[5,1]-map[3,3]-map[2,4]-map[1,5];
             ok:=inrange(4,2);
             if ok then ok:=okdiag2;
           end;
        11:begin
             map[3,2]:=sum-map[1,2]-map[2,2]-map[4,2]-map[5,2];
             ok:=inrange(3,2);
             if ok then ok:=okcol(2);
           end;
        12:check12;
        13:check13;
      end;
      if ok then if l=13 then save else search(l+1);
    end;
  end;
begin
  assign(fin,'prime3.in');
  reset(fin);
  readln(fin,sum,map[1,1]);
  close(fin);

  calprime;

  sols:=0;
  search(1);

  for i:=1 to sols-1 do
    for j:=i+1 to sols do
      if sol[i]>sol[j] then begin t:=sol[i];sol[i]:=sol[j];sol[j]:=t;end;

  assign(fout,'prime3.out');
  rewrite(fout);
  for i:=1 to sols do begin
    if i>1 then writeln(fout);
    for j:=1 to 5 do
      writeln(fout,copy(sol[i],j*5-4,5));
  end;
  close(fout);
end.