In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Dany jest ciąg przedziałów domkniętych , gdzie . 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 i są ustawione w rosnącej kolejności wtedy i tylko wtedy, gdy .
Napisz program, który:
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita , spełniająca nierówność . Jest to liczba przedziałów. W -szym wierszu pliku, , znajduje się opis przedziału w postaci dwóch liczb całkowitych i oddzielonych pojedynczym odstępem, będących odpowiednio jego początkiem i końcem, .
W kolejnych wierszach standardowego wyjścia 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 danych wejściowych:
5 5 6 1 4 10 10 6 9 8 10
poprawną odpowiedzią jest:
1 4 5 10
Autor zadania: Wojciech Guzicki.