Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2017-03-13 16:53:13.
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.

De exemplu permutarea (1,3,4,2,5,6) este o permutare dublă de ordin 3, de trei ori în creştere, pentru că secvenţele (1,3,4) şi (2,5,6) formează şiruri crescătoare, iar toate perechile formate din elementele de pe poziţii identice: (1,2), (3,5), (4,6) formează deasemenea şiruri crescătoare.
Următoarele permutări duble nu au proprietatea de trei ori în creştere:
(1,4,3,2,5,6) –secvenţa (1,4,3) nu este crescătoare,
(1,3,4,2,6,5) - secvenţa (2,6,5) nu este crescătoare,
(1,4,5,2,3,6) –perechea (4,3) nu este crescătoare.
Pentru simplificare în continuare permutarea dublă de trei ori în creştere se va numi permutare.
Vom considera toate permutările de ordin n ordonate lexicografic, numerotate începând cu 1. Tabelul de mai jos conţine datele pentru n=3:

Date de intrare

Fişierul de intrare permutare4.in ...

Date de ieşire

În fişierul de ieşire permutare4.out ...

Restricţii

... ≤ ... ≤ ...

Exemplu

permutare4.in	permutare4.out
This is some text written on multiple lines.	This is another text written on multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

infoarena informatica de performanta