Quasi-palindromi

Fase Territoriale 2010

Un numero palindromo è un numero che letto da destra a sinistra o da sinistra a destra produce la stessa sequenza di cifre.
Un numero N è quasi-palindromo se è palindromo oppure è tale che sostituendo alcune delle cifre 0 presenti in N con altre cifre diverse da 0 si ottiene un numeroN’ che è palindromo.

Ad esempio N=4504 è quasi-palindromo perché sostituendo 0 con 5 si ottiene il numero N’=4554 che è palindromo.

Un insieme di M numeri con lo stesso numero di cifre forma un rettangolo quasi-palindromo (le cui righe sono i numeri) se le cifre nella stessa colonna formano sempre un numero quasi-palindromo.

Ad esempio 120, 046 e 123 formano un rettangolo quasi-palindromo (notare che alcuni numeri possono iniziare con lo zero).
È sufficiente porli nelle righe come segue, per verificarlo colonna per colonna:

120
046
123

Infatti, la cifra 0 in 120 va sostituita con 3 per ottenere un palindromo sulla terza colonna.

Scrivere un programma che dati M numeri di N cifre ciascuno, li stampi in ordine (uno per riga) in modo tale che formino un rettangolo quasi-palindromo.

Dati di input

Il file input.txt è composto da M+1 righe.
La prima riga contiene due interi positivi M e N separati da uno spazio.
Ciascuna delle successive M righe contiene una sequenza di N cifre decimali consecutive (senza separazione di spazi), che rappresenta uno degli M numeri.

Dati di output

Il file output.txt è composto da M righe contenenti gli M numeri in ingresso ordinati in modo da formare un rettangolo quasi-palindromo.

Assunzioni

  • 2 ≤ N, M ≤ 8.
  • Viene garantito che esiste sempre una soluzione.
  • Alcuni numeri possono iniziare con una o più cifre 0.

Esempi di input/output

input.txt output.txt
2 O

----