tperm

TPerm

== include(page="template/taskheader" task_id="tperm") ==

Poveste si cerinta...

Trei informaticieni romani au inventat un nou algoritm care genereaza toate cele $N!$ permutari cu $N$ elemente intr-o ordine specifica, pe care au numit-o *ordinea transpozitiilor*. Algoritmul porneste cu permutarea $1 2 3 .. N$. Apoi alege o pereche de $2$ elemente adiacente (localizate unul langa altul in permutare) si le interschimba. In felul acesta se obtine o permutare noua. Apoi se aplica aceeasi procedura asupra permutarii noi, obtinandu-se o alta permutare s.a.m.d. pana cand au fost generate (exact o data) toate cele $N!$ permutari. Va dati seama ca algoritmul trebuie sa fie destul de destept pentru a genera toate permutarile exact o data (fara repetitii).
 
Din fericire, dumneavoastra nu va trebui sa inventati un astfel de algoritm. De fapt, vi se dau fisierele 'perm.pas':problema/tperm?perm.pas si 'perm.cpp':problema/tperm?perm.cpp , care sunt $2$ implementari ale acestui algoritm, in Pascal si C/C++. Ele citesc numarul intreg $N$ de la intrarea standard si afiseaza in fisierul $perm.txt$ toate cele $N!$ permutari, cate una pe linie, in ordinea in care le genereaza algoritmul.
 
Ceea ce trebuie sa faceti dumneavoastra este, data fiind o permutare, sa aflati pe ce pozitie se afla aceasta in sirul permutarilor generate de algoritm. Pozitiile sunt numerotate de la $1$ la $N!$.

h2. Date de intrare

...

Prima linie a fisierului de intrare $tperm.in$ contine numarul intreg $N$, reprezentand numarul de elemente ale permutarii. A doua linie contine cele $N$ elemente ale permutarii, separate prin cate un spatiu.

h2. Date de iesire

...

In fisierul de iesire $tperm.out$ veti afisa pozitia pe care se afla permutarea in sirul permutarilor generate de algoritm.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100$

h2. Exemplu
table(example). |_. tperm.in |_. tperm.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|4
2 3 1 4
|17

|
h3. Explicatie

...

Lansati in executie cele $2$ programe pentru $N=4$ si veti observa ca permutarea $2 3 1 4$ se va afla pe a $17$-a linie a fisierului $perm.txt$.

== include(page="template/taskfooter" task_id="tperm") ==

2300