== include(page="template/taskheader" task_id="permutare4") ==
Poveste şi cerinţă...
Definim o permutare dublă de ordin <tex>N</tex> ca fiind un şir format din primele <tex>2 * N</tex> numere naturale nenule:
h2. Date de intrare
<tex> P_{1} </tex>, <tex> P_{2} </tex> ... <tex> P_{N} </tex>, <tex> P_{N + 1} </tex>, <tex> P_{N + 2} </tex> ... <tex> P_{2 * N} </tex>
Fişierul de intrare $permutare4.in$ ...
Această permutare dublă este de trei ori în creştere, dacă sunt adevărate următoarele trei proprietăţi:
h2. Date de ieşire
# *Secventa formata din primele* <tex> N </tex> *elemente este crescatoare:*
<tex> P_{1} < P_{2} < ... < P_{N} </tex>
# *Secvenţa formată din ultimele* <tex> N </tex> *elemente este crescătoare:*
<tex> P_{N + 1} < P_{N + 2} < ... < P_{2 * N} </tex>
# *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>
În fişierul de ieşire $permutare4.out$ ...
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:
h2. Restricţii
* <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. 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") ==
