IOI'94 - Giorno 1 - Problema 3: Numeri primi

|---|---|---|---|---|
| 1 | 1 | 3 | 5 | 1 |
|---|---|---|---|---|
| 3 | 3 | 2 | 0 | 3 |
|---|---|---|---|---|
| 3 | 0 | 3 | 2 | 3 |
|---|---|---|---|---|
| 1 | 4 | 0 | 3 | 3 |
|---|---|---|---|---|
| 3 | 3 | 3 | 1 | 1 |
|---|---|---|---|---|  (Figura 1)

La Figura 1 mostra un quadrato in cui ogni riga, ogni colonna e le due diagonali contengono un numero primo di cinque cifre. Le righe vanno lette da sinistra a destra, le colonne dall'alto verso il basso, e le diagonali da sinistra a destra. Usando i dati contenuti nel file INPUT.TXT scrivete un programma che costruisca un quadrato di questo tipo.

La somma delle cifre dei numeri primi deve essere sempre la stessa (11 nell'esempio).
La cifra nell'angolo in alto a sinistra è predeterminata (1 nell'esempio).
Lo stesso numero primo può comparire più volte nello stesso quadrato.
Se esistono più soluzioni, devono essere prodotte tutte.
Un numero primo non può iniziare con degli zero; ad esempio 00003 NON è considerato un numero valido.

Dati di input

Il programma legge i dati dal file INPUT.TXT. Per prima cosa compare la somma delle cifre, seguita dalla cifra che si dovrà trovare nell'angolo in alto a sinistra: il file contiene quindi solo due righe. Ci sarà sempre almeno una soluzione possibile. Nel nostro esempio:

11
1

Dati in output

Nel file OUTPUT.TXT, vengono scritte cinque righe per ciascuna soluzione: ogni riga è costituita da un numero ci cinque cifre. L'esempio presentato ha 3 soluzioni, e quindi il file OUTPUT.TXT avrà il seguente contenuto (le righe vuote sono opzionali):

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.