Énoncé:
Dans un tableau triangulaire d'entiers positifs et négatifs, on souhaite trouver un sous-triangle tel que la somme des nombres qu'il contient soit la plus petite possible.
Dans l'exemple ci-dessous, on peut facilement vérifier que le triangle marqué remplit cette condition avec une somme de $-42$.
Nous souhaitons réaliser un tel tableau triangulaire de mille lignes, nous générons donc 500500 nombres pseudo-aléatoires sk dans l'intervalle ±219, en utilisant un type de générateur de nombres aléatoires (connu sous le nom de Générateur Congruentiel Linéaire) comme suit :
$t := 0$
pour $k = 1$ jusqu'à $k = 500500$:
$$t := (615949 \times t + 797807) \mod 2^{20}$$
$$s_k := t-2^{19}$$
$\\$
Ainsi : $s_1 = 273519$, $s_2 = -153582$, $s_3 = 450905$, etc.
Notre tableau triangulaire est alors formé en utilisant les nombres pseudo-aléatoires ainsi :
$s_1$
$s_2$ $s_3$
$s_4$ $s_5$ $s_6$
$s_7$ $s_8$ $s_9$ $s_{10}$
...
Les sous-triangles peuvent commencer à n'importe quel élément du tableau et s'étendre aussi loin que l'on veut (en prenant les deux éléments directement inférieurs de la ligne suivante, les trois éléments directement inférieurs de la ligne suivante, et ainsi de suite).
La "somme d'un sous-triangle" est définie comme la somme de tous les éléments qu'il contient.
Trouvez la plus petite somme de sous-triangles possible.
Lien du problème originel