Fişierul intrare/ieşire:tperm.in, tperm.outSursăRomanian Open Contest, TIMUS 2001
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.025 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

TPerm

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 si 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!.

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.

Date de iesire

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

Restrictii

  • 1 ≤ N ≤ 100

Exemplu

tperm.intperm.out
4
2 3 1 4
17

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content