Module: Méthode des lignes de balayage


Problem

1 /4


Couverture minimale

Theory Click to read/hide

Problem

Un certain ensemble de segments avec des coordonnées entières d'extrémités \([L_i, R_i]\) est donné sur une ligne. Parmi l'ensemble donné, choisissez un sous-ensemble de segments qui couvre complètement le segment \([0, M]\), (M — nombre naturel) contenant le plus petit nombre de segments.
 
Entrée
La première ligne contient la constante M (\(1<=M<=5000\)). Chaque ligne suivante contient une paire de nombres Li et Ri (\(|L_i|,|R_i| < 50000\)), qui spécifie les coordonnées des extrémités gauche et droite des segments. La liste se termine par une paire de zéros. Le nombre total de segments ne dépasse pas 100 000.
 
Sortie
Sur la première ligne du fichier de sortie, imprimez le nombre minimum de segments requis pour couvrir le segment \([0; M]\). Ensuite, sortez une liste du sous-ensemble de couverture, triée par ordre croissant par les coordonnées des extrémités gauches des segments. La liste des segments est sortie dans le même format que dans l'entrée. Les deux zéros de fin ne sont pas obligatoires. Si le segment \([0; M]\) est l'ensemble original de segments \([L_i, R_i] \)< /span> n'est pas possible, une seule phrase “Pas de solution” doit être sortie.

 

Exemples
1
-1 0
-5 -3
2 5
0 0
1
-1 0
0 1
0 0
# Entrée Sortie
1 Aucune solution
2 1
0 1

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!