Sauvegarde Instable – Qualification 2026

Level 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$

Runtime constraints

Maximum memory usage
100000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
1
4 1 2
Sample output
reussie
Note

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.

Sample input
2
5 2 3
4 2 2
Sample output
impossible
Note

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.

Submit your solution

You have to register or log in to be able to submit your solution.