Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2017-03-13 17:23:14.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	permutare4.in, permutare4.out	Sursă	OJI 2017, Clasele 11-12
Autor	Zoltan Szabo	Adăugată de	Vlad Dumitru-Popescu •depevlad
Timp execuţie pe test	0.75 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Permutare4

Definim o permutare dublă de ordin $N$ ca fiind un şir format din primele $2 * N$ numere naturale nenule:

$P_{1}$ , $P_{2}$ ... $P_{N}$ , $P_{N + 1}$ , $P_{N + 2}$ ... $P_{2 * N}$

Această permutare dublă este de trei ori în creştere, dacă sunt adevărate următoarele trei proprietăţi:

Secventa formata din primele $N$ elemente este crescatoare:
$P_{1} < P_{2} < ... < P_{N}$
Secvenţa formată din ultimele $N$ elemente este crescătoare:
$P_{N + 1} < P_{N + 2} < ... < P_{2 * N}$
Perechile ordonate formate din elementele aflate pe pozitii identice ale celor doua secvente sunt, de asemenea, in ordine crescatoare:
$P_{1} < P_{N + 1}$ , $P_{2} < P_{N + 2}$ , ... $P_{N} < P_{2 * N}$

De exemplu, permutarea $(1, 2, 4, 2, 5, 6)$ este o permutare dubla de ordin $3$ , de trei ori in crestere, intrucat secventele $(1, 3, 4)$ si $(2, 5, 6)$ formeaza siruri crescatoare, iar toate perechile formate din elementele de pe pozitii identice: $(1, 2)$ , $(3, 5)$ , $(4, 6)$ formeaza, de asemenea, siruri crescatoare.
Urmatoarele permutari duble nu sunt de trei ori crescatoare:

$(1, 4, 3, 2, 5, 6)$ : Secventa $(1, 4, 3)$ nu este crescatoare.
$(1, 3, 4, 2, 6, 5)$ : Secventa $(2, 6, 5)$ nu este crescatoare.
$(1, 4, 5, 2, 3, 6)$ : Perechea $(4, 3)$ nu este crescatoare.

Pentru simplitate, permutarea dubla de trei ori in crestere se va numi permutare.
Vom considera toate permutarile de ordin $N$ , ordonate lexicografic si numerotate incepand cu $1$ . Tabelul de mai jos contine datele pentru $N = 3$ :

Pozitie	Permutare
1	1 2 3 4 5 6
2	1 2 4 3 5 6
3	1 2 5 3 4 6
4	1 3 4 2 5 6
5	1 3 5 2 4 6

Exista doua tipuri de intrebari:

Ce permutare se afla pe o pozitie data?
- Codificata
  - $1$ : Tipul intrebarii.
  - $N$ : Ordinul permutarii.
  - $P$ : Pozitia permutarii cerute.
Pe ce pozitie se afla o permutare data?
- Codificata
  - $2$ : Tipul intrebarii.
  - $N$ : Ordinul permutarii.
  - $P_{1} \ P_{2} \ ... \ P_{2 * N}$ : Elementele permutarii.

Ca exemple:

Intrebarea $(1 \ 3 \ 2)$ inseamna: Ce permutare de ordin $3$ se afla pe pozitia $2$ in ordine lexicografica? Raspunsul este $(1 \ 2 \ 4 \ 3 \ 5 \ 6)$ .
Intrebarea $(2 \ 3 \ 1 \ 3 \ 5 \ 2 \ 4 \ 6)$ inseamna: Pe ce poziţie se află permutarea de ordin $3: \ (1 \ 3 \ 5 \ 2 \ 4 \ 6)$ ? Raspunsul este $5$ .