Module: Tarama yöntemi


Problem

1 /4


Asgari kapsam

Theory Click to read/hide

Problem

Bir satırda, bitiş noktalarının tamsayı koordinatlarına sahip belirli bir parça seti \([L_i, R_i]\) veriliyor. Verilen küme arasından, segmenti tamamen kapsayan bir segment alt kümesi seçin \([0, M]\), (M — doğal sayı) en küçük parça sayısını içerir.
 
Giriş
İlk satır, M sabitini içerir (\(1<=M<=5000\)). Sonraki her satır bir sayı çifti içerir Li ve Ri (\(|L_i|,|R_i| < 50000\)), segmentlerin sol ve sağ uçlarının koordinatlarını belirtir. Liste bir çift sıfır ile biter. Toplam segment sayısı 100.000'i geçmez.
 
Çıktı
Çıktı dosyasının ilk satırına \([0; M]\) segmentini kaplamak için gereken minimum segment sayısını yazdırın. Ardından, segmentlerin sol uçlarının koordinatlarına göre artan düzende sıralanan kaplama altkümesinin bir listesini çıkarın. Segment listesi, giriştekiyle aynı formatta çıkarılır. Sondaki iki sıfır gerekli değildir. \([0; M]\) segmenti, \([L_i, R_i] segmentlerinin orijinal kümesiyse \)< /span> mümkün değil, tek bir “Çözüm yok” cümlesi çıktılanmalıdır.

 

Örnekler

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!

# Girdi Çıktı
1
1
-1 0
-5 -3
2 5
0 0
 Çözüm yok
2
1
-1 0
0 1
0 0
 1
0 1