VIII Olimpiada Informatyczna 2000/2001
|
Zadanie: PRZ
|
Autor: Wojciech Guzicki
|
Zawody I stopnia |
Plik źródłowy: | PRZ.??? (np. pas, c, cpp) |
Plik wykonywalny: | PRZ.exe |
Plik wejściowy: | PRZ.in |
Plik wyjściowy: | PRZ.out |
Dany jest ciąg n przedziałów domkniętych [ai; bi], gdzie i=1,2,...,n. Suma tych przedziałów może być przedstawiona w postaci sumy parami rozłącznych przedziałów domkniętych. Zadanie polega na znalezieniu przedstawienia tej sumy w postaci sumy minimalnej liczby parami rozłącznych przedziałów domkniętych. Przedziały tworzące to przedstawienie należy zapisać w pliku wyjściowym w rosnącej kolejności. Mówimy, że dwa przedziały rozłączne [a; b] i [c; d] są ustawione w rosnącej kolejności wtedy i tylko wtedy, gdy a <= b < c <= d.
Napisz program, który:
W pierwszym wierszu pliku tekstowego PRZ.IN znajduje się jedna liczba całkowita n, spełniająca nierówność 3 <= n <= 50000. Jest to liczba przedziałów. W (i+1)-szym wierszu pliku, 1 <= i <= n, znajduje się opis przedziału [ai; bi] w postaci dwóch liczb całkowitych ai i bi oddzielonych pojedynczym odstępem, będących odpowiednio jego początkiem i końcem, 1 <= ai <= bi <= 1000000.
W kolejnych wierszach pliku tekstowego PRZ.OUT należy zapisać opisy znalezionych parami rozłącznych przedziałów. W każdym wierszu ma być zapisany opis jednego przedziału w postaci dwóch liczb całkowitych oddzielonych pojedynczym odstępem, będących odpowiednio początkiem i końcem tego przedziału. Przedziały w pliku wyjściowym powinny być zapisane w rosnącej kolejności.
Dla pliku wejściowego PRZ.IN:
5 5 6 1 4 10 10 6 9 8 10
poprawną odpowiedzią jest plik wyjściowy PRZ.OUT:
1 4 5 10