W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Rozważmy zbiór składający się z domkniętych (zawierających końce) pionowych odcinków na płaszczyźnie. Żadne dwa odcinki ze zbioru nie mają wspólnych punktów. Mówimy, że dwa odcinki z się widzą, jeżeli istnieje poziomy odcinek, który je łączy i nie ma punktów wspólnych z żadnymi innymi odcinkami ze zbioru .
Na poniższym rysunku znajduje się przykładowy zbiór odcinków. Pary widzących się odcinków to: 1-2, 1-3, 2-3, 1-5 i 4-5. Odcinki 1 i 4 się nie widzą.
Dla danej liczby , poszukujemy -elementowego zbioru pionowych odcinków, w którym jak najwięcej par odcinków się widzi.
Napisz program, który:
Pierwszy i jedyny wiersz wejścia zawiera jedną liczbę całkowitą () - liczbę odcinków w poszukiwanym zbiorze.
Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą - maksymalną liczbę par widzących się odcinków. Kolejnych wierszy powinno opisywać odpowiednie rozmieszczenie odcinków - po jednym odcinku w wierszu. Wiersz -szy (dla ) powinien zawierać trzy liczby całkowite: , i (, ), pooddzielane pojedynczymi odstępami i opisujące odcinek o końcach i .
Jeżeli istnieje wiele poprawnych rozmieszczeń odcinków, to Twój program może wypisać dowolne z nich.
Dla danych wejściowych:
4poprawną odpowiedzią jest:
6 1 1 5 2 2 4 3 3 5 4 1 4
Autor zadania: Jakub Radoszewski.