Prologin, le concours national d'informatique

Énoncé¶

Joseph Marchand, devenu un employé de bureau à la vie morose, a installé sur son tableur une application pour générer au hasard des matrices remplies de nombres entiers afin de faire semblant de travailler. Un jour d'ennui profond, son quotidien est bouleversé par le surgissement impromptu de la Réponse Universelle : il remarque en effet que la somme de chaque ligne de son tableau est un multiple de 42, et qu'il en est de même pour les colonnes.

Joseph se demande alors s'il ne serait pas possible de rendre encore plus manifeste l'universalité du Quarante-Deux. Il aimerait pour cela arrondir chaque case de son tableau au multiple inférieur ou supérieur de 42, de sorte que la matrice ne contienne plus que des multiples de 42, sans pour autant que les sommes des lignes ou des colonnes, signes initiaux du miracle, ne s'en trouvent affectées.

Sur chaque case du tableau se trouvent deux boutons + et − qui lui permettront respectront respectivement d'incrémenter et de décrémenter le nombre que cette case contient. Aidez Joseph Marchand à célébrer la Réponse Universelle, sans pour autant attraper un syndrome du canal carpien.

Entrée¶

L'entrée comprendra :

sur la première ligne, un entier naturel n ;
sur les n lignes suivantes, une matrice carrée n×n d'entiers naturels.

Sortie¶

Vous afficherez en sortie le nombre minimal de clics que Joseph doit effectuer pour obtenir un tableau respectant les conditions spécifiées dans l'énoncé. Il est toujours possible d'y parvenir (pourquoi ?).

Contraintes¶

1 ≤ n ≤ 42
les coefficients de la matrice seront compris entre 0 et 1 764.

Contraintes d'exécution

Utilisation mémoire maximum: 1000 kilo-octets
Temps d'exécution maximum: 1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

Exemple de sortie

Commentaire

Ici, les seules cases que l'on peut modifier sont les 4 coins, les autres étant déjà divisibles par 42 et donc égales aussi bien à l'arrondi au multiple inférieur de 42 qu'à l'arrondi au multiple supérieur de 42.

Il y a deux façons d'arrondir. On peut cliquer deux fois sur chaque coin (soit 8 clics au total) pour obtenir le tableau

1
2
3

42 0 0
0 84 0
0 42 42

dont on constate que les sommes des lignes et les sommes des colonnes sont bien les mêmes que le tableau de départ. Il y a une autre façon d'arrondir en respectant les contraintes, mais comme elle nécessite 160 clics, elle n'est pas optimale.