Corrigé X-ENS 2025 Informatique B MP-PC-PSI — Partie I (Q1 à Q4) : Sauts et chemins

Sujet officiel du concours X-ENS, session 2025, épreuve Informatique B MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Une grille $N \times N$ porte en chaque case $(i, j)$ une pénalité entière (un gain est une pénalité négative), stockée dans une liste de listes T : T[i][j]. Un chemin part de $(0, 0)$ et cherche à rejoindre $(N - 1, N - 1)$ ; son poids est la somme des pénalités de ses cases. Un saut $(i, j) \to (i + δ i, j + δ j)$ est le couple (di, dj) ; sauts est la liste des sauts permis par défaut. Une case bonus, une fois atteinte, ajoute des sauts permis pour la suite : le dictionnaire bonus associe à la case (i,j) la liste des sauts qu'elle active. Exemple du sujet (sauts $\to$ , $↙$ , $↘$ par défaut, case bonus grisée en $(1, 2)$ activant $↓$ ) :


T = [[2, -4, -6, 0], [1, -2, 2, 3], [-2, 2, -3, 4], [-1, 4, -3, 7]]
sauts = [(0, 1), (1, -1), (1, 1)]
bonus = {(1, 2): [(1, 0)]}
# le chemin optimal de la figure (c), de poids -7 :
chemin = [(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3)]

Seules sont permises sur les listes len, l'accès l[i], append (coût $O (1)$ ), la concaténation, range, pop(0), le test in, la copie l[:] (coût linéaire) ; sur les dictionnaires, le test in, l'accès, l'affectation et le parcours.

Q1. Écrire poids(T, chemin) ; donner sa complexité.
Q2. Écrire appliquer_sauts(i, j, sauts), qui applique dans l'ordre les sauts depuis $(i, j)$ et renvoie la case atteinte.
Q3. Écrire sauts_corrects(sauts, bonus, chemin), qui teste si chaque saut du chemin est permis.
Q4. Un saut vérifie () si $δ i > 0$ ou ( $δ i = 0$ et $δ j > 0$ ) ; cette condition interdit les cycles. Écrire sauts_bien_formes(sauts, bonus), qui teste () pour tous les sauts, par défaut et bonus.

Corrigé

Q1. On cumule les pénalités des cases du chemin.


def poids(T, chemin):
    total = 0
    for (i, j) in chemin:        # chaque case du chemin, dans l'ordre
        total = total + T[i][j]  # on ajoute sa pénalité
    return total

Invariant de boucle : après le traitement des $k$ premières cases, total est la somme de leurs pénalités ; en fin de boucle, c'est le poids du chemin (et $0$ pour le chemin vide). Sur l'exemple, poids(T, chemin) vaut $2 - 4 - 6 - 2 + 2 - 3 - 3 + 7 = - 7$ , et le chemin (b) pèse $- 6$ (vérifié en exécution). Complexité : la boucle fait $ℓ = len(chemin)$ tours, chacun d'un coût constant (deux accès indexés, une addition, une affectation) ; la fonction est en $O (ℓ)$ , indépendamment de $N$ .

Q2. On fait évoluer deux variables locales, sans réaffecter les arguments i et j, comme le demandait le jury.


def appliquer_sauts(i, j, sauts):
    (a, b) = (i, j)              # case courante
    for (di, dj) in sauts:       # sauts appliqués dans l'ordre de la liste
        a = a + di
        b = b + dj
    return (a, b)

Invariant : après $k$ tours, $(a, b)$ est la case atteinte depuis $(i, j)$ par les $k$ premiers sauts. Sur l'exemple, les sauts du chemin (c) appliqués depuis $(0, 0)$ mènent à $(3, 3)$ . Coût $O (len(sauts))$ .

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →