Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]
Trévor le singe a été placé dans une réserve animalière artificielle. Il apparait immédiatement que la forêt n'est pas naturelle : tous les arbres ont été plantés selon une grille parfaite, chaque arbre étant séparé d'1 mètre de ses voisins. Les arbres de cette forêt sont si proches les uns des autres, qu'aucune grosse branche ne peut pousser et par conséquent, Trévor n'a pas d'endroit tranquille où se reposer. Il résoud ce problème en construisant un certain nombre N de nids, placés sur certains arbres.

Les responsables de la réserve ont délimité le territoire de Trévor par un carré de S mètres de côté, situé bien à l'intérieur de la réserve. Tous les nids de Trévor se trouvent à l'intérieur de ce carré, ou sur sa frontière. Trévor est autorisé à sortir de son territoire, mais la réserve est si grande que même s'il le fait, il n'a aucune chance d'en atteindre les limites.

Comme toutes les branches sont petites, il est plutôt risqué pour un gros singe comme Trévor, de passer d'arbre en arbre. Pour cette raison, le seul moyen dont il dispose pour passer d'arbre en arbre est de se balancer grâce à des lianes, comme le lui a enseigné Tarzan dans sa jeunesse. Dans cette forêt, on trouve toujours des lianes facilement là où on en a besoin, ce qui en fait un moyen de transport rapide et efficace. Il y a cependant des restrictions :

  • Pour pouvoir se balancer entre deux arbres, il ne doit y avoir aucun autre arbre le long de la ligne droite qui les relie (sinon, paf le singe).
  • La longueur des lianes ne permet de se déplacer qu'à des distances de L ou moins, en un saut.

Sauter de liane en liane est fatiguant, même pour un singe bien entraîné, et Trévor souhaite minimiser sa fatigue quand il se déplace entre ses nids. Pour passer d'un nid à l'autre, il utilise des lianes d'arbre en arbre et peut se reposer sur d'autres nids le long du chemin. Comme ces pauses lui permettent de bien reprendre son souffle, Trévor ne mesure pas sa fatigue par le nombre total de sauts. Il mesure en fait sa fatigue par le plus grand nombre de sauts consécutifs qu'il doit effectuer à la suite sans se reposer.

Trévor est très fainéant et pas si intelligent : c'est un vrai singe. Il souhaite que vous l'aidiez à trouver un groupe d'au moins N/2 nids entre lesquels il peut se déplacer, de telle sorte que la plus grande fatigue qu'il doive endurer pour se déplacer entre toute paire de ces N/2 nids soit aussi petite que possible. Si N est impair, alors N/2 doit être arrondi à l'entier supérieur.

Limites de temps et de mémoire (Python)

  • Temps : 0,5 s sur une machine à 1 GHz.
  • Mémoire : 64 000 ko.

Contraintes

  • 1 <= L <= 15, où L est la distance maximale pour un balancement.
  • 2 <= S <= 200, où S est la longueur du côté du territoire de Trévor.
  • 2 <= N <= 1000, où N est le nombre de nids que Trévor a construit.
  • 0 <= Xi < S et 0 <= Yi < S, où (Xi, Yi) sont les coordonnées du ième nid.

De plus, dans 30% des jeux de tests, on vous garantit que L <= 3, S <= 100 et N <= 65.

Entrée

La première ligne de l'entrée contient l'entier L, donnant la distance maximale qui peut être traversée en un seul saut (mesurée en mètres).

La deuxième ligne de l'entrée contient l'entier S, indiquant la longueur du côté du territoire carré (mesuré en mètres également).

La troisième ligne de l'entrée contient l'entier N, indiquant le nombre total de nids.

Chacune des N lignes suivantes contient deux entiers Xi et Yi séparées par un espace, donnant les coordonnées x et y de chaque nid. Deux nids ne se trouvent jamais sur le même arbre.

Sortie

La sortie doit consister en une simple ligne contenant un entier : la fatigue minimale que Trévor doit endurer pour pouvoir se déplacer partout dans un groupe d'au moins N/2 nids.

Exemple

entrée :

3
6
5
0 0
0 3
5 1
5 5
1 5

sortie :

2

Commentaires

Le jeu d'entrée ci-dessus décrit la forêt illustrée ci-dessous. Les arbres sont représentés par des disques noirs et les cinq nids sont indiqués par les lettres A, B, C, D et E. Notez que dans cet exemple, on peut se balancer à une distance maximale de L = 3 mètres.

Considérez les nids A et B. Bien qu'ils soient à trois mètres d'écart, Trévor ne peut pas se balancer directement entre eux, car d'autres arbres sont sur le passage. Il doit donc effectuer au moins deux sauts. Par exemple, il peut se balancer de A=(0,0) à (-1,2), puis repartir vers B=(0,3). Ce chemin est représenté par un segment sur la carte. Notez que ce trajet sort du territoire de Trévor (ce qui est tout à fait autorisé).

Pour se déplacer entre les nids A et E, Trévor a besoin d'au moins trois sauts. Une fois de plus, il ne peut pas prendre un chemin plus direct, car des arbres sont dans le passage. Un chemin possible de A à E peut être de A=(0,0) à (1,2), puis vers (2,3) et finalement vers E=(1,5).

Remarquez que Trévor peut se déplacer de A à E avec une fatigue de seulement 2. Il peut le faire en allant de A à B en deux sauts, puis se reposer sur le nid B, et finalement passer de B à E avec un saut supplémentaire. Comme il effectue au plus deux balancements consécutifs sans se reposer, la fatigue totale pour ce déplacement de A à E est de 2.

Souvenez-vous que Trévor recherche un groupe de trois nids (N/2 arrondi au dessus) entre lesquels il puisse se déplacer. S'il choisit les nids A, B et E, on voit qu'il peut atteindre tout nid à partir de tout autre parmi ce groupe, avec une fatigue maximale de 2. Il n'y a pas d'autre groupe de trois nids qui donne un meilleur résultat (bien qu'il y ait de nombreux autres groupes qui donnent le même résultat), et 2 est donc la réponse finale.

Score

Le score pour chaque jeu d'entrée sera de 100% si la réponse correcte est fournie, et de 0% sinon.

Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.

Correction en cours de chargement…