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):