(*

I primi (IOI 1994)
Copyright (C) 2000 Paolo Boldi

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*)
program Ioi9413;

(* Per rendere pi— efficiente la ricerca delle soluzioni, il programma
   inizialmente ricerca i numeri primi che soddisfano le condizioni
   richieste e li dispone in una trie. Una trie Š un albero in cui ogni
   nodo ha al pi— dieci figli, uno per ogni possibile cifra *)

const
     maxprimi=10000;
     nomefin='input-4.txt';
     nomefout='myout-4.txt';
     DEBUG=true;

type
    ptrie=^trie;
    trie=array ['0'..'9'] of ptrie;
    direzione=(oriz,vert,diag1,diag2);

var
   primi: longint; (* Numero di primi trovati *)
   sc: byte; (* Somma delle cifre *)
   pr: array [1..maxprimi] of longint; (* Array dei primi trovati *)
   tg: ptrie; (* Trie contenente i primi di 5 cifre con somma sc *)
   sk: array [1..5,1..5] of char; (* Soluzione corrente *)
   fin,fout: text; (* File di input e di output *)

procedure instrie(s: string; var t: ptrie);
(* Inserisce la stringa s nella trie t *)
var i: char;
begin
     if (t=nil) then
        begin
             new(t);
             for i:='0' to '9' do t^[i]:=nil
        end;
     if (length(s)>0) then
        instrie(copy(s,2,length(s)-1),t^[s[1]])
end;

function godown(s: string; t: ptrie): ptrie;
(* Restituisce un puntatore alla trie che si ottiene da t scendendo
   lungo s *)
begin
     if (t=nil) then godown:=nil
     else
         if (length(s)>0) then
            godown:=godown(copy(s,2,length(s)-1),t^[s[1]])
         else godown:=t
end;

function sommacar(s: string): byte;
(* Somma le cifre di s *)
var tot,i: byte;
begin
     tot:=0;
     for i:=1 to length(s) do
         tot:=tot+ord(s[i])-ord('0');
     sommacar:=tot
end;

procedure sieve;
(* Riempie l'array pr e la trie tg con i primi la cui somma di cifre sia sc *)
var i,j: longint;
    s: string;
    primo: boolean;
begin
     primi:=0; tg:=nil;
     for i:=2 to 99999 do
         begin
              primo:=true;
              for j:=1 to primi do
                  if (i mod pr[j]=0) then
                     begin
                          primo:=false;
                          break
                     end;
              if (primo) then
                 begin
                      primi:=primi+1;
                      pr[primi]:=i;
                      str(i,s);
                      if (i>9999) and (sommacar(s)=sc) then
                         instrie(s,tg)
                 end
         end
end;

function frammento(x,l: byte; d: direzione): string;
(* Restituisce la stringa ottenuta leggendo l caratteri dalla matrice sk;
   in particolare: se d=oriz, i primi l caratteri della riga x; se d=vert,
   i primi l caratteri della colonna x; se d=diag1, i primi l caratteri
   della diagonale \; se d=diag2, i primi l caratteri della diagonale / *)
var i: byte;
    s: string;
begin
     s:='';
     case (d) of
          oriz: for i:=1 to l do s:=s+sk[x,i];
          vert: for i:=1 to l do s:=s+sk[i,x];
          diag1: for i:=1 to l do s:=s+sk[i,i];
          diag2: for i:=1 to l do s:=s+sk[6-i,i]
     end;
     frammento:=s
end;

procedure out;
(* Emette la soluzione sk sul file fout *)
var i,j: byte;
begin
     for i:=1 to 5 do
         begin
              for j:=1 to 5 do
                  write(fout,sk[i,j]);
              writeln(fout)
         end;
     writeln(fout);
     if (DEBUG) then writeln('Emessa soluzione')
end;

procedure fill(i,j: byte);
(* Prova a riempire la posizione i,j in modo compatibile con i caratteri
   gia' presenti e passa all'elemento successivo; riempie per colonna:

   x....        x....          xxx..          xxxxx         xxxxx
   .....        x....          xxx..          xxxx.         xxxxx
   .....   -->  .....  --> --> xx...  --> --> xxxx. --> --> xxxxx
   .....        .....          xx...          xxxx.         xxxxx
   .....        .....          xx...          xxxx.         xxxxx

   i=indice di riga, j=indice di colonna;
   notate che quando i=j il frammento di diag1 Š gi… disponibile;
   quando 6-i=j il frammento di diag2 Š disponibile solo se i=1 e j=5 *)
var t1,t2,t3,t4: ptrie;
    c: char;
begin
     t1:=godown(frammento(i,j-1,oriz),tg); (* Framm. orizzontale *)
     t2:=godown(frammento(j,i-1,vert),tg); (* Framm. verticale *)
     if (i=j) then
        t3:=godown(frammento(0,i-1,diag1),tg); (* Framm. su diag1 *)
     if (i=1) and (j=5) then
        t4:=godown(frammento(0,4,diag2),tg); (* Framm. su diag2 *)
     for c:='0' to '9' do
         begin
              if (t1<>nil) and (t1^[c]<>nil) and
                 (t2<>nil) and (t2^[c]<>nil) and
                 ((i<>j) or ((t3<>nil) and (t3^[c]<>nil))) and
                 ((i<>1) or (j<>5) or ((t4<>nil) and (t4^[c]<>nil))) then
                 begin
                      sk[i,j]:=c;
                      if (i<5) then fill(i+1,j)
                      else
                          if (j<5) then fill(1,j+1)
                          else out
                 end
         end
end;

(*** MAIN ***)
begin
     assign(fin,nomefin);
     assign(fout,nomefout);
     reset(fin);
     readln(fin,sc);
     read(fin,sk[1,1]);
     if (DEBUG) then writeln('Somma cifre=',sc,'  Cifra iniziale=',sk[1,1]);
     rewrite(fout);
     sieve;
     if (DEBUG) then writeln('Sto per produrre le soluzioni');
     fill(2,1);
     close(fout)
end.