Odcinki

Limit pamięci: 32 MB

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.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę ,
• wyznaczy takie ułożenie pionowych odcinków, że:
  • żadne dwa z nich nie mają wspólnych punktów,
  • liczba par spośród nich, które się widzą jest maksymalna,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz wejścia zawiera jedną liczbę całkowitą () - liczbę odcinków w poszukiwanym zbiorze.

Wyjście

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:

4

6
1 1 5
2 2 4
3 3 5
4 1 4

Autor zadania: Jakub Radoszewski.