QUIZ N°5 : Test Connaissances en Algorithmique

Questions d'algorithmique

Vous pouvez testez vos réponses sur le site d'entraînement

1.
À vos montres !

En épreuve machine de demi-finale, vous soumettrez des solutions pour divers problèmes. On vous donne six variables entières représentant trois heures de soumission (données sous la forme de deux entiers, l'un pour les heures et l'autre pour les minutes). Écrivez une fonction qui renvoie l'heure de la première soumission.

Exemple :
16 42
15 50
16 25
Réponse :
La première heure de soumission est 15 heures 50.


2.
GPS

On vous donne une liste de coordonnées de type (Xi, Yi) (nombres entiers) représentant les coordonnées cartésiennes sur une carte de France des différents centres d'examen pour les demi-finales. Vous vous situez en (x,y). Ecrivez une fonction qui renvoie le centre le plus proche de vous. Vous utiliserez des distances euclidiennes pour vos calculs.

Exemple :
(1, 2) ; (5, 7) ; (10, 15) ; (5, 4) ; (10, 11). Vous vous situez en (5, 5).
Réponse :
Le point le plus proche de (5, 5) est (5, 4).


3.
Le fil d'Ariane

TTY, la chatte mythique de Prologin, est perdue dans le campus de Polytechnique. Celui-ci est donné sous la forme d'un labyrinthe rectangulaire, où une case est soit vide, soit un mur infranchissable. Votre tâche est de rassurer, le cas échéant, TTY : écrivez une fonction qui prenne en entrée la position de TTY, la position de sa gamelle, et le labyrinthe, et renvoie si elle peut ou non atteindre sa gamelle. Il n'est pas possible d'aller en diagonale, seuls les déplacements horizontaux et verticaux sont autorisés. TTY et sa gamelle se situent sur une case vide.

Exemple :
TTY commence en haut à gauche et sa gamelle est en bas à gauche. Un point représente une case vide, et une croix un mur.
...X
XX..
....
.XXX
Réponse :
La réponse est oui.


4.
Cargo

Un avion cargo peut contenir exactement 2*N conteneurs, alignés sur deux rangées de N conteneurs chacune. Chaque conteneur a un poids, et le poids d'une rangée est la somme des poids des conteneurs dans celle-ci. Pour équilibrer l'avion, on veut répartir les conteneurs dans les deux rangées de façon à ce que leur différence de poids (en valeur absolue) soit minimale. Étant donnés les poids des 2*N conteneurs, écrivez une fonction qui renvoie ce minimum.

Exemple :
N=2
Poids : 1 3 8 9
Réponse :
1