Examen Python M1ES 2019/2020

Examen Python M1ES 2019/2020

Les problèmes de cet examen sont de la même forme que ceux que vous avez rencontrés
sur France-IOI. Pour cet examen, vous pouvez revoir le cours de France-IOI mais vous
ne devez pas consulter d’autres sites. Vous ne devez pas communiquer avec une autre
personne. Le code que vous soumettez doit être le vôtre.
Parmi les problèmes qui vous sont proposés, le premier est normalement le plus facile,
et le dernier est un peu complexe et ne comptera que comme bonus.
Après l'heure de fermeture annoncée, aucune réponse ne pourra être déposée : prenez les
devants et n'attendez pas le dernier moment pour transmettre votre code.
Attention ! Vous ne pourrez pas revenir en arrière : une fois votre code validé pour une
question, vous ne pourrez pas le modifier.

Efficacité

Certaines questions mettent l’accent sur l’efficacité de votre code : ce sera annoncé dans leur
présentation. Dans ce cas, les points que vous obtiendrez pour ces questions dépendront de la
rapidité d’exécution de votre code dans des cas où les entrées et sorties sont éventuellement
longues.
Pour les autres questions, un code valide suffit.
Fonctions interdites

Les fonctions et structures suivantes ne doivent être utilisées dans aucun des exercices de
cet examen :
Les fonctions sort, sorted
Les fonctions sum, mean, reduce
L’opérateur in pour tester si une valeur appartient à une liste
Les ensembles (set) et dictionnaires (dict)

Commentaires

Vous pouvez ajouter des commentaires dans votre code si vous pensez qu’il y a des choses
intéressantes à expliquer sur son fonctionnement (par exemple sens des variables utilisées), mais
ce n’est pas obligatoire.
Vous pouvez également vous en servir si vous voulez m’informer d’un problème rencontré.

Notation

Ce n’est pas parce que votre code produit le résultat attendu sur l’exemple que vous aurez tous les
points :
il se peut que votre code ne fonctionne pas sur d’autres exemples, il se peut que votre code ne soit
pas assez rapide…
Ce n’est pas parce que votre code ne produit pas le résultat attendu sur l’exemple que vous
n’aurez aucun point :
si vous avez commencé à écrire quelque chose d’intéressant, même si cela n’est pas abouti, vous
pourrez obtenir quelques points.

----------------------------------------------------------------------
Question 1/6

Comptage

On dispose des dimensions d’un nombre N de rectangles.

On cherche à compter le nombre de ces rectangles qui sont des carrés.

Entrée
Sur la première ligne : le nombre N.

Sur la deuxième ligne, les largeurs (entières) des rectangles, séparées par des espaces.

Sur la troisième ligne, les longueurs (entières) des rectangles, séparées par des espaces.

Sortie
Le nombre de carrés parmi les rectangles.

Exemple
Entrée fournie à votre programme :

10
4 10 5 8 1 10 9 10 3 17
6 10 30 100 100 30 9 10 4 18

Sortie de votre programme :

3
--------------------------------------------------------
Question 2/6

Recherche

On dispose d’une liste L d’entiers triés dans l’ordre croissant, et on cherche le plus grand d’entre
eux qui soit inférieur à un seuil donné.

Entrée
La première ligne contient les entiers de la liste L (dans l’ordre croissant), séparés par des
espaces.

La deuxième ligne contient un seuil entier S.

Sortie
Le programme doit écrire le plus grand nombre de L qui est inférieur ou égal à S.

Contraintes
Le programme doit être le plus rapide possible.

Exemple
Entrée fournie à votre programme :

-20 -15 -4 1 1 2 4 6 6 10 12 17 20 50 100

15

Sortie de votre programme :

12
-------------------------------------------------------------------------
---
Question 3/6

Mémoire

L’objectif de ce problème est de concilier efficacité espace et temps pour le calcul d’une étape du
jeu de la vie.
Processus
Le jeu de la vie définit un processus de transformation d’une image binaire (image contenant des
pixels qui sont soit blancs soit noirs).
Dans ce processus, la valeur d’un pixel est transformée de la façon suivante :

Un pixel blanc entouré d’exactement trois pixels noirs (sur 8) devient noir ;
un pixel noir entouré de deux ou trois pixels noirs (sur 8) reste noir ;
dans les autres cas, le pixel devient (ou reste) blanc.
Entrée
La première ligne de l’entrée est formée du nombre C de colonnes et du nombre L de lignes de
l’image.

Les L lignes suivantes sont les lignes de l’image : les pixels blancs sont représentés par des points,
et les pixels noirs par le caractère #.

Sortie
La sortie doit être constituée des L lignes de l’image transformée par une étape du jeu de la vie.

Contraintes
Votre programme doit être aussi rapide que possible, et doit consommer de la mémoire de manière
indépendante de L. Vous pouvez donc déclarer des variables de taille C (ou de taille constante),
mais pas de variable de taille L ou dépendant de L.

Les entrées fournies vérifieront toujours 3<L<100000 et 3<C<1000.

Exemple
Entrée fournie à votre programme :

16 12
................
.......#######..
...###########..
...###......##..
.....###........
.......###......
.........####...
.......###......
.....###........
...###.......#..
.######....###..
....##########..

Sortie de votre programme :

........#####...
....##.......#..
...#..........#.
...#.....##..#..
.....#.#........
.......#.#.#....
...........#....
.......#.#.#....
.....#.#........
.......#.....#..
..#.....##....#.
..#....####..#..
----------------------------------------------------------------------------
Question 4/6

Attente

Les mesures de distanciation physique rendent l’accès aux transports en commun plus compliqué.
Des files d’attente sont organisées aux arrêts de bus, afin de laisser la priorité aux personnes
qui sont arrivés en premier à l’arrêt.

On cherche à suivre l’état de la file d’attente à un arrêt de bus au cours du temps.

Le programme recevra en entrée N commandes décrivant l’arrivée de groupes de personnes

(avec le nombre de personnes dont ils sont constitués), le passage des bus (avec le nombre de
places disponibles dedans) ou demandant l’état de la file d’attente (nombre de groupes dans la file,
taille du premier groupe).

On suppose que quand un bus arrive, les groupes montent dedans tant qu’il reste de la place.
Si par exemple il reste 2 places mais que le premier groupe de la file d’attente est formé de 4
personnes,
personne ne monte et le bus part (avec ses deux places libres).

Les commandes peuvent être de trois formes :

avec une commande A, on signale l’arrivée d’un groupe de personnes.

avec une commande B, on signale le passage d’un bus.
avec une commande Q, on demande quel est le nombre de groupes de personnes qui attendent à
l’arrêt.

Entrée

La première ligne est le nombre N de commandes. Chacune des N lignes suivantes contient la
lettre correspondant au type de commande, éventuellement suivi du nombre associé (le nombre de
personnes dans le groupe avec A, le nombre de places libres à l’arrivée du bus avec B). Ce
nombre est toujours un entier.

Sortie

À chaque commande Q, le programme doit écrire une ligne contenant le nombre de groupes de
personnes qui attend à l’arrêt, ainsi que le nombre de personnes constituant le premier groupe de
la file (ou 0 si il n’y en a pas).

Contraintes

On cherchera à écrire le programme le plus rapide possible. On suppose qu’avec les données
fournies en entrée, la fille d’attente ne dépasse jamais 1000 groupes.

Exemple
Entrée fournie à votre programme :

24
A3
A4
A1
A2
Q
B8
Q
A5
A3
A1
A4
B4
Q
A5
A2
Q
A1
A1
B 15
Q
B4
Q
B 10
Q

Sortie de votre programme :

43
12
45
65
45
45
00
-------------------------------------------------------------------------
-------------------
Question 5/6

Ordre

On dispose de deux listes L1 et L2 de nombres entiers, tous différents, qui sont toutes les deux
ordonées dans l'ordre croissant.

On considère la liste L formée de tous les nombres contenus dans L1 ou L2, ordonnée.

On cherche à déterminer la liste de départ à laquelle appartient le N-ième élément de L, pour un

entier N donné, de la manière la
plus efficace possible.

Entrée
La première ligne est constituée des éléments de L1, séparés par des espaces.

La deuxième ligne est constituée des éléments de L2, séparés par des espaces.

La troisième ligne contient le nombre N.

Sortie
Le numéro (1 ou 2) de la liste de départ à laquelle apartient le N-ième élément de L.

Exemple
Entrée fournie à votre programme :

1 4 10 17 22 23 36 54 78
2 5 11 12 16 18 20 88 90 123 143
10
Sortie de votre programme :

2
---------------------------------------------------------------

Question 6/6

Labyrinthe

Vous devez écrire un programme qui dessine un labyrinthe créé au hasard, de taille donnée.
Les murs du labyrinthe sont constitués du caractère #, et les chemins par des espaces.
L’entrée du labyrinthe se trouve en bas à droite et la sortie en haut à gauche. Dans ce labyrinthe,
il ne doit exister qu’un seul chemin pour aller de l’entrée à la sortie.

Hasard

Pour introduire du hasard, vous pourrez utiliser les fonctions python de la bibliothèque random.

Chargez tout d’abord cette bibliothèque grâce à la commande import random en début de
programme.
Si tab est un tableau, random.shuffle(tab) mélangera ce tableau de façon aléatoire, et random.
sample(tab,n) retournera un tableau de n éléments de tab choisis au hasard.

Entrée
La première ligne de l’entrée contient deux entiers séparés par un espace : la largeur L et la
hauteur
H du labyrinthe. Ces deux entiers seront toujours impairs.

Sortie
Vous devez écrire H lignes contenant chacune L caractères, formant un labyrinthe.

Exemple
Entrée fournie à votre programme :

23 11

Sortie possible de votre programme :

# #####################
## # # # #
# # # # # # ### # # # #
### # ### ##
# # ######### # ##### #
## # ## ##
# ##### ### # # # # # #
# # ## ###
##### ############# # #
# ##
##################### #