Le déluge – Qualification 2016
Niveau 1

Énoncé

Il y a fort longtemps, existait un continent où vivait une espèce rare : le Prolosaure. Ce
continent était composé de N montagnes (numérotées de 1 à N) de différentes altitudes dans
lesquelles les paisibles dinosaures vivaient en paix.

Un jour, une tempête se déchaîna et entraîna une montée globale du niveau de l’eau. Les
Prolosaures se demandent si une partie de leur foyer a disparu sous les eaux.

On vous donne une liste de nombres représentant les altitudes des différentes montagnes qui
composent le continent ainsi que l’altitude globale atteinte par la montée des eaux. Écrivez un
programme qui indique si au moins une montagne a été submergée par les flots.

Entrée

L’entrée comprendra :

 un entier relatif h correspondant à l’altitude atteinte par la mer ;
 sur la ligne suivante, un entier naturel non nul N correspondant au nombre de
montagnes ;
 sur la ligne suivante, N entiers relatifs yi séparés par des espaces, représentant
l’altitude de chaque montagne.

Sortie

Vous afficherez en sortie :

 1 si au moins une montagne a été submergée, c'est-à-dire que son altitude est
strictement inférieure au niveau de la mer ;
 0 sinon.

Contraintes

 -1 000 ≤ h ≤ 1 000 ;
 1 ≤ N ≤ 100 ;
 -1 000 ≤ yi ≤ 1 000.

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
500 millisecondes
Exemples d'entrée/sortie

Exemple d'entrée
-91
13
-41 -47 -52 -57 -74 -77 -23 -14 -56 2 -74 -40 -59
Exemple de sortie
0




Montée des eaux – Qualification 2016
Niveau 2

Énoncé

Le grand conseil des Prolosaures, un groupe plus malin que la plupart de leurs congénères,
cherche un moyen de calculer le volume gagné par la mer lors du déluge.

On vous donne une liste de nombres représentant les altitudes des différentes montagnes qui
composent le continent ainsi que l’altitude globale atteinte par la montée des eaux. Écrivez un
programme qui indique le volume total de l’eau au-dessus des zones inondées, sachant que la
surface du sommet de chaque montagne vaut 1. Par exemple, si l'altitude d'une montagne est
20 et que l'altitude de l'eau est 23, alors cette montagne contribue pour un volume de 3 unités
(voir exemples).

Entrée

L’entrée comprendra :

 un entier relatif h correspondant à l’altitude atteinte par la mer ;
 sur la ligne suivante, un entier naturel non nul N correspondant au nombre de
montagnes ;
 sur la ligne suivante, N entiers relatifs yi séparés par des espaces, représentant
l’altitude de chaque montagne.

Sortie

Vous afficherez en sortie :

 Le volume total V d’eau au-dessus des terres submergées.

Contraintes

 -100 000 ≤ h ≤ 100 000 ;
 1 ≤ N ≤ 10 000 ;
 -100 000 ≤ yi ≤ 100 000 ;
  0 ≤ V ≤ 100 000 000.

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
-91
13
-41 -47 -52 -57 -74 -77 -23 -14 -56 2 -74 -40 -59
Exemple de sortie
0




La prophétie – Qualification 2016
Niveau 3

Énoncé

Le grand conseil des Prolosaures a mis la main sur une tablette très ancienne annonçant le
désastre que les dinosaures sont en train de vivre. Sur cette pierre oubliée de tous, il est
indiqué le volume d’eau qui est en train de noyer le monde. Pour anticiper le désastre, le
conseil cherche à savoir jusqu’à quelle altitude la mer va continuer de monter.

On vous donne une liste de nombres représentant les altitudes des différentes montagnes qui
composent le continent ainsi que le volume total d’eau au-dessus des terres submergées.
Écrivez un programme qui indique l’altitude (arrondie à l'entier inférieur) que va atteindre
l’eau une fois la catastrophe terminée. Plus précisément, étant donné le volume V d'eau
déversé par la tempête, on vous demande de trouver l'entier h tel que : - si le niveau de la mer
est h, alors le volume de l'eau sur les zones inondées est au plus V ; - si le niveau de la mer est
h+1, alors le volume d'eau sur les terres est strictement supérieur à V.

Entrée

L’entrée comprendra :

 un entier relatif V représentant le volume d'eau issu de la tempête ;
 sur la ligne suivante, un entier naturel non nul N correspondant au nombre de
montagnes ;
 sur la ligne suivante, N entiers relatifs yi séparés par des espaces, représentant
l’altitude de chaque montagne.
Sortie

Vous afficherez en sortie :

 L’arrondi inférieur h de l’altitude qui sera atteinte par l’eau une fois la tempête
terminée.

Contraintes

 0 ≤ V ≤ 100 000 000 ;
 1 ≤ N ≤ 10 000 ;
 -100 000 ≤ yi ≤ 100 000 ;
 -100 000 ≤ h ≤ 100 000.

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
0
13
-41 -47 -52 -57 -74 -77 -23 -14 -56 2 -74 -40 -59
Exemple de sortie
-77




Après le déluge – Qualification 2016
Niveau 4

Énoncé

Grâce aux prévisions avérées du grand conseil des Prolosaures, un certain nombre de
survivants au déluge ont pu se réfugier sur quelques îles émergées. Pour communiquer, un
pacte a été conclu avec les Algoptéryx, dinosaures volants, grâce auxquels les bases de la
communication ont pu s'établir entre les différentes îles. Malheureusement, ceux-ci
commmencent à se lasser de leur rôle trop peu rémunérateur.

En guise de solution, le grand conseil des Prolosaures a imaginé déployer un grand réseau de
téléphones yaourt entre les îles, grâce au concours des Algoptéryx.
Malheureusement, le fil nécessaire à leur confection se fait rare en ces temps post-
apocalyptiques, et une récompense est prévue pour celui qui en minimisera l'usage.

Écrivez un programme qui permet de déterminer la longueur de fil minimale nécessaire pour
rallier les différentes îles : toute île doit être reliée à au moins une autre île.

Entrées

L'entrée comprendra :

 un entier naturel n représentant le nombre d'îles à rallier sur la première ligne ;
 sur chacune des n lignes suivantes, les coordonnées entières relatives x et y d'une île,
séparées par une espace.

Sortie

Vous afficherez en sortie :

 un entier représentant la longueur de fil minimale nécessaire, arrondie à l'entier inférieur.

Contraintes

 1 ≤ n ≤ 1 000 ;
 -10 000 ≤ xi, yi ≤ 10 000.

Contraintes d'exécution

Utilisation mémoire maximum

1000 kilo-octets

Temps d'exécution maximum

1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

4
-1664 -2941
1969 -4009
7953 -5787
-1136 -1206
Exemple de sortie

11842
Un peu de compagnie – Qualification 2016
Niveau 5

Énoncé

Une nouvelle problématique vient troubler la quiétude post-apocalyptique des Prolosaures :
suite à la solitude qui règne sur leurs îles, les Prolosaures en sont venus à se détester, de telle
sorte que la plupart d'entre eux ont au moins un rival à haïr. Le téléphone yaourt, qui ne
permet pas les communications simultanées, sert alors de carburant, alimentant la haine entre
rivaux.

Le grand conseil, préoccupé par la situation, pense avoir trouvé une solution : sur l'une des
îles se trouvait une fabrique de talkie-walkies, fonctionnant par paires, dont la portée permet
de couvrir toute l'étendue de l'archipel Prolosaure.

Il suffirait que ne soient mis en contact que des couples de Prolosaures entretenant de bonnes
relations, en prenant garde à ne laisser personne dans la solitude. Il n'est par contre pas
nécessaire de rallier un même individu à plusieurs autres, à moins que leurs rivalités ne
l'imposent.

Toutefois, les talkie-walkies se font rares, et le conseil en vient à se demander s'il sera un jour
possible de mettre ce plan à exécution.

À partir du nombre d'îles et d'une liste de couples d'îles dont les habitants ne souhaitent pas
communiquer avec ceux de l'autre île, écrivez un programme qui indique le nombre minimal
de couples de talkie-walkies nécessaires. On vous garantit qu'aucun Prolosaure n'est détesté
de tous.

Entrée

L'entrée comprendra :

 sur la première ligne, un entier naturel représentant le nombre d'îles à rallier, noté n ;
 sur la seconde ligne, un entier représentant le nombre de rivalités animant les
Prolosaures, noté m ;
 sur les m lignes suivantes, des couples d'identifiants d'îles (entiers compris entre 0 et
n-1) indiquant que leurs occupants se détestent, séparés par une espace (on note que
les paires fournies ne sont pas redondantes, et que le premier identifiant sera toujours
inférieur au second).

Sortie

Vous afficherez en sortie :

 le nombre minimal de paires de talkie-walkies nécessaires pour que chaque île dispose
d'au moins un talkie-walkie et ne communique qu'avec des Prolosaures non hostiles.

Contraintes
  1 ≤ n ≤ 200 ;
 1 ≤ m ≤ n(n-1)/2.

Contraintes d'exécution

Utilisation mémoire maximum
5000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
8
5
0 5
0 1
1 7
0 2
3 4
Exemple de sortie
4
Commentaire


(NB: le positionnement des îles est arbitraire.)

Ici, 4 talkie-walkies ont été nécessaires.

Exemple d'entrée
4
3
0 1
0 2
1 2
Exemple de sortie
3
Commentaire


(NB: le positionnement des îles est arbitraire.)

Ici, 3 talkie-walkies ont été nécessaires.