![](/static/branding/mistrzostwa/map_logo.jpg)
![](/static/branding/mistrzostwa/nask_logo.png)
![](/static/branding/mistrzostwa/cp_logo.png)
![](/static/branding/mistrzostwa/uwr_logo.png)
![](/static/branding/mistrzostwa/fri_logo.png)
![](/static/branding/mistrzostwa/insert_logo.png)
Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2023
Problem description
VMPC (Variably Modified Permutation Composition) jest funkcją, która jako wejście otrzymuje permutację f liczb ze zbioru {0, 1, …, N − 1} i jako wyjście również zwraca permutację g liczb z tego samego zbioru.
Wzór funkcji jest niezwykle prosty: g(x) = f(f(f(x))+1) gdzie wszystkie obliczenia wykonywane są modulo N.
Weźmy dla przykładu permutację f równą (1,5,6,4,0,2,3) (to znaczy f(0) = 1, f(1) = 5, f(2) = 6, …, f(6) = 3). Wówczas permutacja g jest równa (3,4,0,5,6,1,2) (na przykład g(5) = f(f(f(5))+1) = f(f(2)+1) = f(6+1) = f(0) = 1).
Twoim zadaniem będzie odwrócić funkcję VMPC to znaczy, dla ustalonej permutacji g odzyskać jaka była permutacja f.
Napisz program, który wczyta permutację g, wyznaczy permutację f i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość permutacji. W drugim wierszu znajduje się ciąg N parami różnych liczb naturalnych Gi, pooddzielanych pojedynczymi odstępami i określających kolejne wartości permutacji g dla kolejnych argumentów 0, 1, 2, …, N − 1.
Wyjście
Jeśli nie istnieje permutacja f spełniająca warunki zadania należy
wypisać na wyjście jedno słowo NIE
. Jeśli zaś permutacja
f istnieje należy w pierwszym
wierszu wypisać TAK
, a w drugim wierszu kolejne wartości
f(0), f(1), …, f(N−1).
Jeśli istnieje więcej niż jedno rozwiązanie, należy wypisać dowolne z nich.
Ograniczenia
1 ≤ N ≤ 20, 0 ≤ Gi ≤ N − 1.
Przykład
Wejście | Wyjście | |
|
|
Wejście | Wyjście | |
|
|