# *Perechile ordonate formate din elementele aflate pe pozitii identice ale celor doua secvente sunt, de asemenea, in ordine crescatoare:*
<tex> P_{1} < P_{N + 1} </tex>, <tex> P_{2} < P_{N + 2} </tex>, ... <tex> P_{N} < P_{2 * N} </tex>
De exemplu, permutarea <tex> (1, 2, 4, 2, 5, 6) </tex> este o permutare dubla de ordin <tex> 3 </tex>, de trei ori in crestere, intrucat secventele <tex> (1, 3, 4) </tex> si <tex> (2, 5, 6) </tex> formeaza siruri crescatoare, iar toate perechile formate din elementele de pe pozitii identice: <tex> (1, 2) </tex>, <tex> (3, 5) </tex>, <tex> (4, 6) </tex> formeaza, de asemenea, siruri crescatoare.
De exemplu, permutarea <tex> (1, 3, 4, 2, 5, 6) </tex> este o permutare dubla de ordin <tex> 3 </tex>, de trei ori in crestere, intrucat secventele <tex> (1, 3, 4) </tex> si <tex> (2, 5, 6) </tex> formeaza siruri crescatoare, iar toate perechile formate din elementele de pe pozitii identice: <tex> (1, 2) </tex>, <tex> (3, 5) </tex>, <tex> (4, 6) </tex> formeaza, de asemenea, siruri crescatoare.
Urmatoarele permutari duble nu sunt de trei ori 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:
* <tex> (1, 4, 3, 2, 5, 6) </tex>: Secventa <tex> (1, 4, 3) </tex> *nu* este crescatoare.
* <tex> (1, 3, 4, 2, 6, 5) </tex>: Secventa <tex> (2, 6, 5) </tex> *nu* este crescatoare.
* <tex> (1, 4, 5, 2, 3, 6) </tex>: Perechea <tex> (4, 3) </tex> *nu* este crescatoare.
*Pentru simplitate, permutarea dubla de trei ori in crestere se va numi permutare.*
Vom considera toate permutarile de ordin <tex> N </tex>, ordonate lexicografic si numerotate incepand cu <tex> 1 </tex>. Tabelul de mai jos contine datele pentru <tex> N = 3 </tex>:
|_. *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 <tex> 1 \ N \ P </tex>
*** <tex> 1 </tex>: Tipul intrebarii.
*** <tex> N </tex>: Ordinul permutarii.
*** <tex> P </tex>: Pozitia permutarii cerute.
# *Pe ce pozitie se afla o permutare data?*
** Codificata <tex> 2 \ N \ P_{1} \ P_{2} \ ... \ P_{2 * N} </tex>
*** <tex> 2 </tex>: Tipul intrebarii.
*** <tex> N </tex>: Ordinul permutarii.
*** <tex> P_{1} \ P_{2} \ ... \ P_{2 * N} </tex>: Elementele permutarii.
Ca exemple:
* Intrebarea <tex> (1 \ 3 \ 2) </tex> inseamna: _Ce permutare de ordin_ <tex> 3 </tex> _se afla pe pozitia_ <tex> 2 </tex> _in ordine lexicografica?_ Raspunsul este <tex> (1 \ 2 \ 4 \ 3 \ 5 \ 6) </tex>.
* Intrebarea <tex> (2 \ 3 \ 1 \ 3 \ 5 \ 2 \ 4 \ 6) </tex> inseamna: _Pe ce poziţie se află permutarea de ordin_ <tex> 3: \ (1 \ 3 \ 5 \ 2 \ 4 \ 6) </tex>_?_ Raspunsul este <tex> 5 </tex>.
Să se răspundă corect la un set de întrebări.
h2. Input:
Fişierul de intrare *$permutare4.in$* contine pe fiecare linie o intrebare de orice tip.
h2. Output:
Fisierul de iesire *$permutare4.out$* va conţine pe câte o linie câte un răspuns la fiecare întrebare din fişierul de intrare, în ordinea întrebărilor.
h2. Restricţii si Precizari:
* <tex> 2 < N < 1000 </tex>.
* Indicele pentru intrebarile de tip 1 respecta: <tex> \ 0 < P \leq 1.000.000.000 </tex>.
* Raspunsul pentru intrebarile de tip 2 respeca: <tex> \ 0 < P \leq 1.000.000.000 </tex>.
* Fisierele de intrare vor contine cel mult <tex> 2.000 </tex> de intrebari.
* Pentru teste in valoare de <tex> 20 </tex> de puncte, numarul de intrebari va fi <tex> 1.000 </tex>, iar numerele de ordine ce intervin in calcule vor fi mai mici decat <tex> 5.000 </tex>.
* Pentru teste în valoare de <tex> 30 </tex> de puncte, întrebările vor fi doar de tipul <tex> 1 </tex>.
* Pentru teste în valoare de <tex> 30 </tex> de puncte, întrebările vor fi dora de tipul <tex> 2 </tex>.
* Pentru teste în valoare de <tex> 30 </tex> de puncte, întrebările vor fi mixte.
* *Conform regulamentului OJI, se vor acorda* <tex> 10 </tex> *puncte din oficiu.*
h2. Date de intrare
Fişierul de intrare $permutare4.in$ ...
h2. Date de ieşire
În fişierul de ieşire $permutare4.out$ ...
h2. Restricţii
h2. Exemplu
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. permutare4.in |_. permutare4.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1 3 2
2 3 1 3 5 2 4 6
1 4 1
2 4 1 2 3 4 5 6 7 8
| 1 2 4 3 5 6
5
1 2 3 4 5 6 7 8
1
|
h3. Explicaţie
h3. Explicaţie:
...
* A doua permutare de ordin <tex> 3: \ (1, 2, 4, 3, 5, 6) </tex>.
* Permutarea <tex> (1, 3, 5, 2, 4, 6) </tex> are pozitia <tex> 5 </tex>.
* Prima permutare de ordin <tex> 4: \ (1, 2, 3, 4, 5, 6, 7, 8) </tex>.
* Permutarea <tex> (1, 2, 3, 4, 5, 6, 7, 8) </tex> are pozitia <tex> 1 </tex>.
== include(page="template/taskfooter" task_id="permutare4") ==
