PermGroup

O funcție bijectivă $p: \{1, 2, ..., N\} \rarr \{1, 2, ..., N\}$ se numeşte permutare de lungime $N$. Pe mulțimea permutărilor de lungime $N$ (notat cu $S_N$) definim operația de compunere ◦ astfel: $p \circ q: \{1, 2, ..., N\} \rarr \{1, 2, ..., N\}$, $(p \circ q)(i) = p(q(i))$.
Putem defini inductiv $p_1 \circ p_2 \circ ... \circ p_k = (((p_1 \circ p_2) \circ p_3) \circ ... \circ p_k)$. Numim subgrup generator al mulțimii $S_N$ orice submulțime $\{p_1, p_2, ..., p_k\} ⊆ S_N$ care respectă proprietatea că orice permutare $X$ din $S_N$ se poate scrie ca $p_{i_1} \circ p_{i_2} \circ ... \circ p_{i_L}$ cu $i_1, i_2, ..., i_L$ alese convenabil, nu neapărat distincte sau crescătoare.
Se consideră, că rezultatul compunerii a zero permutări este permutarea identică ($p(i)=i$ pentru orice $1 ≤ i ≤ N$).

Cerință

Se dă un număr natural nenul $N$. Se cere să se construiască un subgrup generator al mulțimii $S_N$.

Interacțiune

Problema este în formatul interactiv. Veți avea de implementat două funcții:

void selectpermgroup (int N);

Această funcție trebuie să aleagă permutările conținute în subgrupul generator. În cadrul acestei funcții, puteți apela funcția

void addperm(int* permutare)

implementată de către comisie, căreia îi dați ca parametru un pointer spre prima poziție dintr-o permutare de lungime $N$ pentru a semnala adăugarea fiecăreia dintre permutări la subgrup. Funcţia selectpermgroup va fi apelată o singură dată pe test. În cadrul acesteia funcţia addperm poate fi apelată de oricâte ori.

Dacă folosiți std::vector din C++ STL, apelați addperm(v.data()).

Se garantează că în implementarea comisiei, funcția addperm va face o copie la permutarea dată ca parametru, deci nu apar probleme dacă refolosiți pointer-ul la aceeași zonă de memorie mai târziu pentru a adăuga altă permutare.

void solve(int N, int* permutare);

Această funcție primește ca parametru același $N$ ca și funcţia precedentă, și un pointer spre primul element al unei permutări de lungime $N$. Trebuie să construiți un șir de permutări din cele alese în funcția anterioară care compuse în ordinea dată să dea permutarea permutare.

Folosiți funcția pusă la dispoziție de comisie

void compose(int id)

pentru a alege următoarea permutare din șirul de compuneri, unde parametrul id reprezintă index-ul permutării (începând de la $0$) în subgrupul ales. Ordinea este consistentă cu cea în care ați apelat funcția addperm în cadrul lui selectpermgroup. La finalul funcției solve, trebuie ca permutarea obținută prin compunerea succesivă a tuturor permutărilor date prin compose să fie egală cu permutarea cerută.

Atenție! Această funcție va fi apelată de mai multe ori în cadrul aceluiași test. La fiecare apel al funcției solve, apelurile funcției compose din apelurile anterioare ale lui solve vor fi ignorate (se începe din nou cu $0$ permutări alese pentru a obține permutarea cerută).

Punctare

Pentru orice test, dacă vreun apel al funcției solve nu obține corect permutarea cerută sau se efectuează vreun apel invalid (addperm în cadrul solve sau compose in cadrul selectpermgroup sau permutări/id-uri invalide în apelurile spre funcțiile comisiei), punctajul pe testul respectiv va fi $0$. Altfel, vom defini costul pe un întreg test ca $│SG│ \times max(C)$, unde $│SG│$ este dimensiunea subgrupului ales și $max(C)$ este numărul maxim de apeluri ale funcției compose în cadrul unui apel al funcției solve. Următorul tabel definește structura punctării testelor:

Exemplu

Interactor:
selectpermgroup(3);
Concurent:
addperm([2,1,3]);
addperm([2,3,1]);
addperm([3,2,1]);
Interactor:
solve([3, 1, 2]);
Concurent:
compose(1); $[2,3,1]$
compose(2); $[2,3,1] \circ [3,2,1]=[1,3,2]$
compose(0); $[1,3,2] \circ [2,1,3]=[3,1,2]$
Interactor:
solve([1, 3, 2]);
Concurent:
compose(0); $[2,1,3]$
compose(1); $[2,1,3] \circ [2,3,1]=[1,3,2]$
Interactor:
OK! $Cost=3 \times max(2,3)=9$