permutare4

Permutare4

# *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:
* <tex> (1, 4, 3, 2, 5, 6) </tex>: Secventa <tex> (1, 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* |

|_. *Pozitie* |_. *Permutare* |

| 1         | 1 2 3 4 5 6 |
| 2         | 1 2 4 3 5 6 |
| 3         | 1 2 5 3 4 6 |

h2. Input:

Fişierul de intrare $permutare4.in$ contine pe fiecare linie o intrebare de orice tip.

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.

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

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. 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") ==