Problem description

Back
Show PDF
Maskotki
(C)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Po posprzątaniu swojego pokoju, Jasiu postanowił ułożyć swoje maskotki w kolejności tego, jak bardzo je lubi. Zmiany będzie dokonywał poprzez przestawienie maskotek na swojej półce.

Pojawił się jednak problem: Jeśli Jasiu zamieni dwie maskotki miejscami, to od razu będzie widać, że jedną faworyzuje i tej drugiej zrobi się smutno. Postanowił on zatem posłużyć się podstępem – zamiast zamieniać miejscami dwie maskotki, będzie obracał cyklicznie trzy maskotki. Oznacza to, że jeśli są trzy parami różne maskotki A, B i C, to może tak zrobić, żeby A stała na starej pozycji B, B na starej pozycji C, a C na starej pozycji A. Pozycje innych maskotek nie ulegają zmianie.

Ponieważ każda maskotka jest inna, Jasiu przypisał każdej z nich unikalną liczbę wi oznaczającą, jak bardzo lubi daną maskotkę. Pomóż mu i powiedz, czy za pomocą wyżej opisanego podstępu jest w stanie ustawić maskotki w kolejności malejącej po poziomie lubienia, a jeżeli tak to powiedz mu, ile oraz jakie podstępy musi wykonać.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę maskotek Jasia. W następnym wierszu znajduje się N liczb wi oznaczających wartości maskotek. Liczby te są parami różne.

Wyjście

W pierwszym wierszu wyjścia powinno znaleźć się jedno słowo TAK lub NIE, oznaczające odpowiednio, że Jasiu może lub nie może za pomocą jakiejś liczby podstępów ustawić maskotki w zadanej kolejności. Jeżeli odpowiedź brzmi TAK, to w drugim wierszu wyjścia powinna być jedna liczba całkowita K, oznaczająca minimalną liczbę podstępów koniecznych, aby uporządkować jego maskotki na półce. W kolejnych K wierszach powinny widnieć trójki liczb ai, bi oraz ci, oznaczające pozycje maskotek A, B i C w i-tym podstępie. Pozycje liczymy od 1. Jeżeli odpowiedź brzmi NIE, to na wyjściu nie powinno być kolejnych wierszy.

Ograniczenia

1 ≤ N ≤ 106,  − 109 ≤ wi ≤ 109, 0 ≤ K ≤ 5 ⋅ 106.

Podzadania

Podzadanie Warunki Punkty
1 N ≤ 6 10
2 N ≤ 500 20
3 N ≤ 5 000 20
4 N ≤ 50 000 20
5 brak dodatkowych ograniczeń 30

Rozwiązania częściowe mogą otrzymać różną część punktów na różnych podzadaniach:

  • Za rozwiązanie wypisujące wyłącznie pierwszy wiersz poprawnie przyznawane będzie 10% punktów.
  • Za rozwiązanie wypisujące pierwsze dwa wiersze poprawnie z optymalną wartością K przyznawane będzie 30% punktów.
  • Za rozwiązanie wypisujące poprawne wyjście z nieoptymalną wartością K, która spełnia warunek K ≤ 4 ⋅ N + 1 000 przyznawane będzie 50% punktów.

Rozwiązanie zawsze powinno wypisać poprawny ciąg operacji, choć niekoniecznie taki, który sortuje wejście.

Przykład

Wejście Wyjście Wyjaśnienie 
6
67 1 100 -67 -100 -1

TAK
2
1 2 3
4 5 6

Pierwsze trzy wartości możemy ustawić malejąco jednym podstępem, tak samo kolejne trzy. Jest to minimalny wynik, ponieważ jeden podstęp wpływa na co najwyżej trzy wartości, a tutaj wszystkie sześć jest nie na swoich miejscach.
Wejście Wyjście Wyjaśnienie 
2
1 2

NIE

Nie można wykonać podstępu (ponieważ nie ma trzech maskotek, a maskotki do podstępu muszą być parami różne), a ciąg nie jest uporządkowany malejąco, zatem nie da się go uporządkować.
Wejście Wyjście Wyjaśnienie 
4
1 4 2 3

TAK
1
1 4 2

Od razu widać, że za pomocą jednego podstępu można uporządkować ciąg. Zauważ, że osoby brane do podstępu nie muszą być tuż obok siebie. Nie ma też żadnych wymogów co do kolejności wypisywanych osób; poprawnymi trzecimi wierszami wyjścia byłyby również 4 2 1 oraz 2 1 4, ale już nie 1 2 4 (jest to inne przesunięcie).