Sauvegarde Instable – Qualification 2026

Niveau 5 ⋅ Validation weight: 10%

Énoncé

Joseph a maintenant réussi à pénétrer dans le bâtiment. Il a trouvé une salle serveur, dans laquelle se trouve sûrement une mine d'information, utile au retour des humains. Avec l'aide de Rob0bit et Roboctet, il souhaite sauvegarder le système.

Le système, assez ancien, est composé de $N$ disques de stockage.

Chaque disque $i$ dispose de sa propre plage de transfert $[A_i, B_i]$, ce qui signifie que chaque opération efface entre $A_i$ et $B_i$ Téraoctets.

Pour éviter un maximum de fragmenter le disque, les opérations ne peuvent être effectuées qu'aux extrémités de celui-ci. Aussi, en raison de l'ancienneté du disque, celui-ci est instable, donc à chaque transfert effectué par Joseph, une autre portion d'un disque quelconque est effacée à jamais.

Si, après un transfert effectué par Joseph, tous les disques ont une quantité de données restantes inférieure à la quantité minimale de données transférables par opération ($A$), alors la sauvegarde est réussie. En revanche, si cela arrive après un effacement incontrôlé, la sauvegarde n'est pas réussie.

Si il est possible de sauvegarder le système avec succès, affichez "reussie". Sinon, affichez "impossible".

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de disques.
  • Sur les lignes suivantes, une liste de N éléments : disques, la liste des disques.
    • Une ligne par élément de la liste : séparés par des espaces, un entier C (la capacité du disque), un entier A (quantité minimale de données transférées par opération), et un entier B (quantité maximale de données transférées par opération).

Sortie

Afficher, sur une ligne, si Joseph peut sauvegarder le système avec succès

Contraintes

  • $1 \le N \le 10$
  • $1 \le C \le 100$
  • $1 \le A \le B \le C$

Contraintes de performance

  • $1 \le N \le 10\,000$
  • $1 \le C \le 1\,000\,000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

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

Ici, le système est composé d'un seul disque de 4 To avec une plage de transfert entre 1 et 2 To.

Joseph peut par exemple commencer par transférer 1 To.

L'instabilité du système entraînera un effacement de 1 à 2 To supplémentaires.

Dans les 2 cas, Joseph peut ensuite transférer 2 To (respectivement 1 To), et la quantité de données restantes est donc de 0.

La sauvegarde est donc réussie.

Exemple d'entrée
2
5 2 3
4 2 2
Exemple de sortie
impossible
Commentaire

Peu importe le transfert de données effectué en premier par Joseph, il est possible que l'instabilité du système efface le reste du disque.

On se retrouve donc dans un cas avec un seul disque.

Encore une fois, peu importe le transfert effectué, l'instabilité du système peut effacer le reste du disque.

Ainsi, la sauvegarde est impossible.