Module: Metodo di scansione


Problem

1 /4


Copertura minima

Theory Click to read/hide

Problem

Su una linea è dato un certo insieme di segmenti con coordinate intere delle estremità \([L_i, R_i]\). Tra l'insieme dato, scegli un sottoinsieme di segmenti che copra completamente il segmento \([0, M]\), (M — numero naturale) contenente il minor numero di segmenti.
 
Input
La prima riga contiene la costante M (\(1<=M<=5000\)). Ogni riga successiva contiene una coppia di numeri Li e Ri (\(|L_i|,|R_i| < 50000\)), che specifica le coordinate delle estremità sinistra e destra dei segmenti. L'elenco termina con una coppia di zeri. Il numero totale di segmenti non supera i 100.000.
 
Uscita
Nella prima riga del file di output stampa il numero minimo di segmenti richiesti per coprire il segmento \([0; M]\). Successivamente, genera un elenco del sottoinsieme di copertura, ordinato in ordine crescente in base alle coordinate delle estremità sinistre dei segmenti. L'elenco dei segmenti viene emesso nello stesso formato dell'input. I due zeri finali non sono obbligatori. Se il segmento \([0; M]\) è l'insieme originale di segmenti \([L_i, R_i] \)< /span> non è possibile, dovrebbe essere emessa una sola frase “Nessuna soluzione”.

 

Esempi
# Input Uscita
1
1
-1 0
-5 -3
2 5
0 0
 Nessuna soluzione
2
1
-1 0
0 1
0 0
 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!