Prologin, the French National Computer Science Contest

Énoncé¶

C'est lors d'un voyage en Grèce que Joseph Marchand eut l'idée de recréer le labyrinthe du minotaure, mais en changeant quelque peu son principe. Son labyrinthe grandeur nature est composé d'une grille de $N$ x $M$ cases. Chaque case renferme une divinité grecque qui attaque le visiteur en lui prenant une part plus ou moins grande de son âme.

Sur la carte vue du dessus on constate que le visiteur démarre sur une des cases en haut et doit rejoindre une des cases en bas. On remarque également que chaque case permet de rejoindre les 3 cases voisines sur la ligne du dessous, menant ainsi vers la sortie après $N$ pas. Heureusement, Joseph donne cette carte, permettant au visiteur d'être informé des divinités présentes dans chaque case ainsi que de leur puissance.

L'objectif est d'arriver à sortir du labyrinthe en conservant un maximum de son âme pour ne pas être transformé en minotaure et rester enfermé à jamais. Comment un visiteur pourrait trouver le meilleur chemin afin de sortir du labyrinthe ?

Entrée¶

L'entrée contiendra:

Sur la première ligne, un entier $A$ représentant l'âme du visiteur.
Sur la ligne suivante, un entier $N$ représentant la longueur (hauteur) du labyrinthe.
Sur la ligne suivante, un entier $M$ représentant la largeur du labyrinthe.
Sur les $N$ lignes suivantes, $M$ entiers représentant la puissance de la divinité à la case de coordonnées ($x$, $y$) (sachant $x$ un entier représentant la distance parcourue depuis l'entrée et $y$ la coordonnée latérale).

NB: la case en haut à gauche est donc la case de coordonnées (0,0). Celle en bas à droite est la case de coordonnées (N-1, M-1).

Sortie¶

Afficher une liste d'entiers correspondant au meilleur chemin permettant de sortir du labyrinthe en conservant un maximum de son âme, sachant que le visiteur augmente sa coordonnée n à chaque case et ne peut revenir en arrière. Il ne faut afficher qu'un seul des chemins possibles.

Si aucun chemin n'est possible, afficher "IMPOSSIBLE".

Contraintes¶

$5 ≤ A ≤ 5000$
$2 ≤ N ≤ 200$
$2 ≤ M ≤ 100$
$0 ≤$ puissance de la divinité $≤ 100$

Contraintes de performance¶

$100 ≤ A ≤ 10000$
$1000 ≤ N ≤ 5000$
$100 ≤ M ≤ 1000$
$0 ≤$ puissance de la divinité $≤ 100$

Runtime constraints

Maximum memory usage: 20000 kilobytes
Maximum execution time: 1000 milliseconds

Input/output samples

Sample input

Sample output

Note

On peut passer par 3 chemins dans cet exemple:

les premier et deuxième chemins nous font passer par des cases de poids 4, 3, 2 et 3
le troisième chemin nous fait passer par des cases de poids 3, 4, 3 et 2

Dans ces 3 cas, le total d'âme consommé est de 12. Sachant que l'âme du visiteur fait 12 points, il peut sortir du labyrinthe (de justesse).