Il existe beaucoup de prophéties de la forme : « La fin du monde aura lieu entre telle année et telle année ». Ainsi, si une prophétie prédit la fin du monde entre l'année 2090 et l'année 2093, la fin du monde pourrait avoir lieu en 2090, 2091, 2092, ou 2093 (4 possibilités).
Étant donné un ensemble de prophéties de cette forme, vous vous posez la question suivante : « si l'on suppose que toutes les prophéties sont vraies, combien y a-t-il d'années distinctes auxquelles la fin du monde pourrait se produire ? ». Écrivez un programme qui répond à cette question. Notez que la réponse peut éventuellement être zéro.
Limites de temps et de mémoire (Python)
- Temps : 1 s sur une machine à 1 GHz.
- Mémoire : 8 000 ko.
Contraintes
- 1 <= nbPropheties <= 10 000, où nbPropheties est le nombre de prophéties
- 0 <= anneeMini <= anneeMaxi <= 10 000, où anneeMini et anneeMaxi sont respectivement l'année minimale et l'année maximale de la fin du monde, d'après la prophétie i.
Entrée
La première ligne de l'entrée contient un entier : nbPropheties.
Chacune des nbPropheties lignes suivantes décrit une prophétie par deux entiers séparés par un espace, anneeMini et anneeMaxi.
Sortie
Vous devez afficher le nombre d'années durant lesquelles la fin du monde peut avoir lieu en respectant toutes les prophéties à la fois.
Pour avoir les 100 points, votre programme doit être aussi efficace que possible.
Exemples
Exemple 1
entrée :
5 7 19 9 25 3 21 11 22 2 17
sortie :
7
Exemple 2
entrée :
6 3 17 9 30 14 19 9 20 1 13 11 22
sortie :
0
Commentaires
Dans le premier exemple les années 11, 12, 13, 14, 15, 16 et 17 font partie de toutes les prophéties, il y a donc 7 années possibles.
Dans le second exemple les prophéties 3 (années 14 à 19) et 5 (années 1 à 13) n'ont aucune année en commun, il y a donc 0 année possible.
Pensez à faire des dessins pour vous représenter le problème.
EXEMPLE DE CODE
Pour vous aider avec la lecture des données d'entrée, vous pouvez prendre comme modèle l'exemple de programme ci-dessous, qui lit la description des prophéties, puis affiche l'entier 42.
#include <stdio.h> int main() { int nbIntervalles; scanf("%d", &nbIntervalles); for (int iIntervalle = 0; iIntervalle < nbIntervalles; iIntervalle = iIntervalle + 1) { int debut, fin; scanf("%d %d", &debut, &fin); } printf("%d\n",42); return 0; }
#include <iostream> using namespace std; int main() { int nbIntervalles; cin >> nbIntervalles; for (int iIntervalle = 0; iIntervalle < nbIntervalles; iIntervalle = iIntervalle + 1) { int debut, fin; cin >> debut >> fin; } cout << 42 << endl; return 0; }
import algorea.Scanner; class Main { public static void main(String [] args) { Scanner input = new Scanner(System.in); int nbIntervalles = input.nextInt(); for (int iIntervalle = 0; iIntervalle < nbIntervalles; iIntervalle = iIntervalle + 1) { int debut = input.nextInt(); int fin = input.nextInt(); } System.out.println(42); } }
Notez bien l'utilisation de algorea.Scanner
, le Scanner de Java étant trop lent et gourmand en mémoire, il est très fortement déconseillé de l'utiliser.
void main() { int nbIntervalles = readInt(); for (int iIntervalle = 0; iIntervalle < nbIntervalles; iIntervalle = iIntervalle + 1) { int debut = readInt(); int fin = readInt(); } println(42); }
let read_int() = Scanf.scanf " %d" (fun x -> x) let nbIntervalles = read_int() let _ = for iIntervalle = 1 to nbIntervalles do let debut = read_int() in let fin = read_int() in () done; print_int 42; print_newline()
program Solution; var iIntervalle, nbIntervalles, debut, fin: LongInt; begin readln(nbIntervalles); for iIntervalle := 1 to nbIntervalles do begin readln(debut, fin); end; writeln(42) end.
nbIntervalles = int(input()) for loop in range(nbIntervalles): debut, fin = map(int, input().split()) print(42)
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 sera mise en ligne après la fin de l'épreuve.