Pyramides – Épreuve régionale 2010

ÉNONCɶ

Cet exercice permettra à Joseph Marchand de descendre une pyramide aux marches glissantes sans se fracturer un os.

Chaque case est dotée d'un degré d'adhérence. Il est donc dans l'intérêt de Joseph de passer par le chemin où il a le moins de chances de glisser.

Son escalier est cependant assez particulier : en effet, lorsque Joseph se trouve sur une case, il ne peut descendre que sur la case en bas à gauche ou sur la case en bas à droite.

ENTRÉE¶

• Un entier N correspondant à la hauteur de la pyramide.
• (N * (N + 1)) / 2 entiers correspondants au degré d'adhérence de chaque case.

SORTIE¶

• Un entier correspondant au maximum de la somme des degrés d'adhérence pour parcourir la pyramide de haut en bas.

CONTRAINTES¶

• N sera plus petit ou égal à 100
• L'adhérence de chaque case sera comprise entre 0 et 1000 (bornes incluses)