X/ENS Informatique B MP-PC-PSI 2024

ECOLE POLYTECHNIQUE - ESPCI
ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2024

JEUDI 18 AVRIL 2024
16h30 - 18h30

FILIERES MP-MPI-PC-PSI
Epreuve n° 8

INFORMATIQUE B (XELSR)

Durée : 2 heures

L'utilisation des calculatrices n'est pas
autorisée pour cette épreuve

Logimage

Le sujet comporte 7 pages, numérotées de 1 à 7.

Un logimage consiste en une grille de n1 lignes et nc colonnes, dans laquelle 
il faut retrouver
une image en noir et blanc à partir de clés. Chaque ligne (et chaque colonne) 
est codée par
une liste de clés entières. Un entier m dans une liste de clés correspond à un 
bloc de m cases
consécutives à colorier en noir. Par exemple, pour une ligne donnée, la liste 
de clés [2,4] signifie
qu'en regardant les cases de cette ligne de gauche à droite, on trouve d'abord 
un certain nombre
(éventuellement nul) de cases blanches, puis un bloc de 2 cases noires 
consécutives, suivi d'au
moins une case blanche, puis un bloc de 4 cases noires, puis éventuellement des 
cases blanches.
De même, la liste de clés pour une colonne décrit la taille des blocs 
rencontrés depuis le haut
jusqu'au bas de la colonne. On veut s'assurer que la solution d'un logimage 
existe et est unique.
La figure 1 présente un exemple de logimage et sa solution : les listes en 
regard des lignes et
des colonnes sont les clés codant la solution. Par exemple, la deuxième ligne 
est codée par une
liste de deux clés : [3,1], alors que la première ligne est codée par une liste 
contenant une seule
clé : [2].

M] | 15] | 4] } 2]
(2
[3,1]
[4
[4
[1,1]
(a) Exemple de logimage (b) Solution

FIGURE 1: Exemple de logimage et sa solution.

Dans ce sujet, nous représenterons les clés des lignes par une liste de listes 
d'entiers, de
même que pour les clés des colonnes. Dans la suite du sujet, cle_1 représentera 
la liste des listes
de clés par lignes, et cle_c la liste des listes de clés par colonnes. Dans 
l'exemple ci-dessus, on
aura donc cle_1=[[2],1[3,1],[41,{[41,[11,1]]. Une solution sol sera représentée 
par une
liste de listes, telle que so1[il][j] représente l'état de la case de la grille 
sur la ligne i et la
colonne j. Un état sera codé par un entier : 0 pour une case blanche et 1 pour 
une case noire.
Complexité. La complexité, ou le temps d'exécution, d'une fonction F est le 
nombre d'opé-
rations élémentaires (addition, multiplication, affectation, test, ...) 
nécessaires à l'exécution
de F. Lorsque cette complexité dépend de plusieurs paramètres n et m, on dira 
que Fa une
complexité en O(b(n,m)) lorsqu'il existe trois constantes À, no et mo telles 
que la complexité
de Fest inférieure ou égale à À - b(n,m), pour tout n > no et m > mo. Lorsqu'il 
est demandé
de donner la complexité d'un programme, le candidat devra justifier cette 
dernière si elle ne
se déduit pas directement de la lecture du code.

Rappels concernant le langage Python. L'utilisation de toute fonction Python 
sur les
listes autre que celles mentionnées dans ce paragraphe est interdite. Si a 
désigne une liste en
Python de longueur n :

-- len(a) renvoie la longueur de cette liste, c'est-à-dire le nombre d'éléments 
qu'elle contient ;
la complexité de Len est en O(1).

-- ali] désigne le i-ème élément de la liste, où l'indice i est compris entre 0 
et len(a) - 1
inclus ; la complexité de cette opération est en O(1).

-- a.append(e) ajoute l'élément e à la fin de la liste a; on supposera que la 
complexité de
cette opération est en O(1).

-- a.pop() renvoie la valeur du dernier élément de la liste a et l'élimine de 
la liste a; on
supposera la complexité de cette opération en O(1).

-- a.copy() fait une copie de la liste a; la complexité de cette opération est 
en O(n).

-- Si f est une fonction, la syntaxe [£f(x) for x in a] permet de créer une 
nouvelle liste,
ayant le même contenu que la liste b résultant de l'exécution du code suivant 
(et avec la
même complexité) :

b = []
for x in a:
b.append(f(x))

Manipulation de solutions. On pourra utiliser dans la suite les fonctions 
suivantes pour
manipuler les solutions :

-- init_sol(nl,nc,v) renvoie une nouvelle solution de n1 lignes et nc colonnes 
dont toutes
les cases sont initialisées à v.

-- copy_sol(sol) renvoie une copie de la solution sol obtenue en créant une 
nouvelle
solution de même taille et en copiant le contenu de chaque case.

La complexité de chacune de ces fonction est en O(nl x nc).

Convention. Dans le sujet, on supposera que nl et nc (qui décrivent le nombre 
de lignes et
le nombre de colonnes de la grille) sont des variables globales accessibles à 
l'intérieur de toutes
les fonctions.

Organisation du sujet. Ce sujet comporte quatre parties, de difficulté 
croissante. La par-
tie IV dépend des résultats de la partie III, autrement les parties sont 
indépendantes.
Partie I -- Préliminaires et vérification d'une solution

Question 1. Ecrire une fonction cases_noires qui prend en argument une liste de 
listes
d'entiers cle_1 représentant les clés des lignes d'un logimage et qui renvoie 
le nombre de cases
à colorier en noir dans la solution. Quelle est la complexité de cette fonction 
?

Question 2. À partir de cle_1l, on peut obtenir le nombre de cases noires de la 
solution,
et de même pour cle_c. Écrire une fonction compatibles qui prend ces deux 
listes de listes
d'entiers en arguments et qui renvoie True 51 et seulement si elles codent le 
même nombre de
Cases noires.

Les règles de construction des logimages imposent au moins une case blanche 
entre deux
blocs dans une solution valide. La clé d'une ligne permet de calculer la taille 
minimale de la
partie de la ligne occupée par les blocs codés. Par exemple, la clé de ligne 
[3,5,2] nécessite
une taille minimale de 12 cases :

Question 3. Ecrire la fonction taille minimale qui prend en argument une liste 
(supposée
non vide) d'entiers représentant les clés d'une ligne et renvoie cette taille 
minimale.

On souhaite maintenant vérifier si une solution est valide. Pour ceci, on 
considère la fonction
verif_ligne ci-dessous, qui a pour but de vérifier que la ligne d'indice i de 
la solution sol ne
contient que des 0 et des 1 et contient tous les blocs décrits par cle_1. On 
peut s'apercevoir
que cette implémentation contient une erreur, qui sera corrigée à la question 
suivante.

1 def verif_ligne(sol, cle_l, i):

2 i_bloc=0

3 taille=0

4 for j in range(nc):

a) couleur _case=sollill;j]

6 if couleur_case=-

7 taille=taille+i

8 if taille>0 and (couleur _case==0 or j+1==nc):

9 if i_bloc 0). On peut exprimer la valeur de M[c] [b] de façon récursive, 
en considérant
les deux cas suivants :

1. Si le dernier bloc pouvait être placé sans la dernière case (M[c-11 [b] > 0) 
et que la
dernière case n'est pas noire (sol_pli_ligne]l[cl! = 1) alors on peut placer ce 
bloc de
la même façon que sans la dernière case, c'est-à-dire M[c] [b] = Mfc-1] [b].

2. Sinon, on regarde si on peut placer le bloc en toute fin de ligne (donc le 
faire commencer
à la case d'indice c -- s + 1). Pour ceci, il faut que les deux conditions 
ci-dessous soient
réunies :

(a) conflit(c-s+1,s) > c (il n'y a pas de conflit avec les cases de la ligne 
jusqu'à c)

(b) Mlc-s-1] [b-1] > 0 (il y a suffisamment de place dans les cases d'indice 0 
à c--s--1
pour placer les blocs précédents, afin de laisser une case blanche à l'indice c 
-- s)

Si ces deux conditions sont vérifiées, alors on peut placer le bloc en position 
EUR -- s +1,
donc Mfc] [b] = c--s+1. Sinon, le dernier bloc ne peut pas être placé : Mc] [b] 
= ---1.

Question 10. On suppose que les valeurs de Mc] TO] ont été précalculées pour 
tout c. Écrire
un algorithme calcul_matrice qui prend M en argument et qui calcule le reste de 
la matrice par
programmation dynamique. La complexité de la fonction devra être en O(nc*) et 
sera justifiée.

Dans le cas du premier bloc (b = 0), une attention particulière doit être 
portée à la première
case noire de la ligne, si elle existe. On note p la position de la première 
case noire si elle existe
(sol_pli_ligne] [p] = 1 et sol_pli_ligne][j] # 1 pour tout j