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]
Le réchauffement climatique est un sujet plutôt chaud en ce moment, un grand nombre de scientifiques tentent de modéliser l'évolution du climat pour les décennies à venir. L'un deux a élaboré une méthode qui, d'après lui, fournit un certain nombre de prévisions quant au climat futur en un point donné de la Terre. Chaque prévision est de la forme: "entre le jour X et le jour Y, la température à cet endroit atteindra un maximum de K degrés", où les paramètres X, Y et K prennent des valeurs entières.

Le scientifique est convaincu que ses prévisions sont extrêmement précises, tandis que vous n'êtes pas aussi sûr que lui. Vous voulez écrire un programme qui indique si, pour un point donné de la Terre, les prévisions du scientifique sont cohérentes. Par cohérent, on entend qu'il est possible de trouver une séquence de températures M1, M2, ... MN, Mi étant la température maximale au jour i, pour lesquelles toutes les prévisions sont satisfaites. Une prévision (X, Y, K) est satisfaite si, entre le jour X et le jour Y (inclus), la température ne dépasse jamais K, et il existe au moins un jour dont la température maximale atteint exactement K.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 16 000 ko.

Contraintes

  • 1 <= T <= 5, où T est le nombre de points sur Terre où vous souhaitez tester la méthode du scientifique;
  • 1 <= N <= 100 000, où N est le nombre de jours étudiés pour un emplacement;
  • 1 <= P <= 50 000, où P est le nombre de prévisions faites pour un emplacement;
  • 1 <= X <= Y <= N, où X et Y sont les jours impliqués dans la prévision (où 1 est le premier jour de la période d'étude et N le dernier);
  • 1 <= K <= 100 000, où K est une température maximale prévue (mesurée en centièmes de degrés Kelvin).

De plus, dans 30% des cas, toutes les périodes d'étude satisferont P <= 100.

Entrée

Votre programme doit lire sur l'entrée standard. La première ligne contiendra un unique entier T, le nombre de points où vous souhaitez tester la méthode du scientifique. Les lignes suivantes contiendront la description des T tests, l'un après l'autre.

Chaque description commence par une ligne contenant les deux entiers N et P, séparés par un espace. Les P lignes suivantes contiennent chacune une prévision. Chaque prévision est décrite par trois entiers X, Y et K, séparés par des espaces.

Sortie

Votre programme doit écrire exactement T lignes sur la sortie standard. La ième de ces lignes doit contenir un unique entier, correspondant à la description du ième test. Pour chaque test, cet entier doit être '1' si les prévisions correspondantes sont cohérentes, ou '0' s'il est impossible de satisfaire toutes les contraintes à cet endroit.

Exemple

entrée :

2
5 3
1 2 2
4 5 1
2 4 3
4 4
3 3 4
4 4 3
1 4 2
1 2 1

sortie :

1
0

Commentaires

Les données d'exemple contiennent deux descriptions de test. Le premier test cherche à vérifier trois prévisions sur une durée de cinq jours. Ces prévisions sont les suivantes:
  • parmi les jours 1 et 2: au moins un jour aura une température maximale de 2, et aucun jour ne dépassera la température 2;
  • parmi les jours 4 et 5: au moins un jour aura une température maximale de 1, et aucun jour ne dépassera la température 1;
  • parmi les jours 2, 3 et 4: au moins un jour aura une température maximale de 3, et aucun jour ne dépassera la température 3.

La séquence de températures 1, 2, 3, 1, 1 satisfait ces prévisions. Par conséquent, cet ensemble de prévisions est cohérent.

Le second test cherche à vérifier quatre prévisions sur une durée de quatre jours. Ces prévisions sont les suivantes:

  • le jour 3 doit avoir une température maximale de 4;
  • le jour 4 doit avoir une température maximale de 3;
  • parmi les jours 1, 2, 3 et 4: au moins un jour aura une température maximale de 2, et aucun jour ne dépassera la température 2;
  • parmi les jours 1 et 2: au moins un jour aura une température maximale de 1, et aucun jour ne dépassera la température 1.

Clairement, la troisième prévision entre en conflit avec les deux premières, donc cet ensemble de prévisions n'est pas cohérent.

Calcul du score

Le score pour chaque test d'entrée sera de 100% si la bonne séquence de réponses est fournie sur la sortie standard, ou 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…